I don't believe that the problem is NP-complete, because you're working in a fixed dimension. Since most of us believe that the hardest case is when the angle between the two lines is very small, then you can take the line L half way in between the two lines, and orthogonally project onto it for the objective function. Then we have an integer programming problem in 2 dimensions -- the two inequalities specify the proper side of the two lines. Hendrik Lenstra in "Integer Programming with a fixed number of variables" in Mathematics of Operations Research, showed that when the dimension is fixed there is a polynomial time algorithm for IP (using a variant of the L^3 lattice basis reduction). There's also the paper http://www.math.uni-klu.ac.at/or/doctoralschool/deloera.pdf "Integer Polynomial Optimization in Fixed Dimension" which mentions that a convex polynomial objective function also has a polynomial time algorithm in fixed dimension, so that should do it for this problem.
[Added Comments] Using the two papers that I mentioned in my comments http://mpi-inf.mpg.de/~soeren/pubs/2ip.ps http://homepages.cwi.nl/~aardal/journal_rev.ps one can proceed as follows: We're going to have upper and lower supporting lines orthogonal to the midpoint line L. These will always have the property that we know that there is at least one lattice point in the quadrilateral bounded by the the original lines and the supporting line (though at the beginning, it has degenerated into a triangle). At the beginning the lower supporting line is the one passing through the intersection of the two original lines. The upper supporting line can be calculated by noticing that any disk of radius > sqrt(2)/2 must contain a lattice point, so you can find the smallest distance along the midline where you can place the center of such a disk -- it will be where the line from center orthogonal to each of the original lines has distance sqrt(2)/2. By simple trigonometry you can see that if the number of bits in the original number is N, then we need at most 2N bits to specify this point (i.e. if the denominators are around n for the originals, then the denominators for the above points are at most n^2). Now use the algorithm in first paper which tells you in time linear in the number of bits of the problem whether or not there are any lattice points in the quadrilateral. Do a binary search by looking at the a test line half way in between the supporting lines, and testing each of the two quadrilaterals. After only about N steps (remember that N is the log of the coefficients) you'll be down to a quadrilateral with a small area and width. At that point you can quickly enumerate all lattice points in it and test them for the minimum. This algorithm probably runs in time O(N^2) where N is the number of bits in the original coefficients.