Have you thought about just using the Lego NXT motors?
http://www.robotc.net/wiki/Tutorials/Arduino_Projects/Mobile_Robotics/Lego/Connecting_A_Lego_Motor
That shows how you can get the motor turning; you'll have to figure out how to use the encoders in some other manner.
http://shop.lego.com/en-US/Interactive-Servo-Motor-9842?CMP=KAC-SAHGOOGLEUS&HQS=9842&adtype=pla
$20.00 USD from the Lego store; that's cheaper than some standard servos (although I doubt the Lego device is as robust?)...