Help with Steering?

[interfect]

Hello,
We have our robot set up with two independent steering wheels, tracked with encoders and run by globe motors geared down at about a 3:1 ratio. It has fallen to me to program this rig, and convince it to do something useful. I am trying to get the wheels to point in a certain direction, but I am having trouble with the position seeking algorithm.
Running the wheels right when they're turned too far left, and left when they are too far right, just makes them oscillate about the target (I didn't add a dead zone. I could try that, but I want them to seek exactly.)
I tried implementing full PID control, but tuning it has already consumed more time than it's really worth, and no matter what I do it either oscillates or doesn't get to the target, or sometimes both.
I think the underlying problem may be that, because of the motors and the gearing, the wheels don't perceptibly move unless the motor is set to more than about 20 units off of idle (127). Once the motor revs up, it's hard to stop on target. PID ought to be able to deal with this, but it isn't.
What sort of control schemes have other people used for this sort of problem? How do you tune your PID loops (if you use them)?

What's the simple & effective solution that I am ignoring?