[another addition to simplify things]:

The idea in solving the problem is to do the following:

1. Find a good enough approximation to the minimum distance, and the lattice point attaining that, so that you can enclose that region in a rectangle whose sides are parallel to the $x$ and $y$ axes, with a small enough area, $A$ and perimeter $P$. It's easy to see that you can enumerate all lattice points inside of such a rectangle in time $A+P$, and then check those to see which ones give you the minimum. [Changing notation] Let $n$ be the number of bits to specify the problem and $N=2^n$. Let the angle between the two lines be denoted by $2 \theta$, and the midline by $L$.

2. As I mentioned, any disk with radius $> \sqrt{2}/2$ must contain a lattice point. We use this by placing such a disk in between the two lines, and as close to the point of intersection as possible. We see that the distance from the intersection point to the center of the disk which just fits, is $\sqrt{2}/2 \csc \theta$. If $\theta \ge \pi/6$ (say) we can enclose the whole triangle bounded by the lines and the tangent line to the disk orthogonal to $L$ in a rectangle of constant size and perimeter, so we just try all of those points. Note that in any case $\theta \ge c/N$ for some absolute constant $c$ since when $\theta$ is small enough $\cos \theta \approx 1 - \theta^2/2$, and $\cos 2 \theta$ is given by a dot product between the coefficients of the lines and so has at most $2n$ bits.

3. Otherwise we call the algorithm described in http://mpi-inf.mpg.de/~soeren/pubs/2ip.ps just once, with the objective function the dot product between $(x,y)$ and a vector parallel to $L$, and the four constraints: between the two lines, and the dot product with $L$ is $\ge 0$ and $\le$ the bound we get by placing the disk. Because $\theta$ is small enough and bounded away from 0, we can now draw a rectangle enclosing the point produced by the algorithm whose area and perimeter are bounded, independent of the number bits, which must contain the answer, and we again enumerate all points in that rectangle.

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.

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.