The micro servos don't seem to have as much variation in the shape of the output shaft as normal servos. Though I may just think this is the case since I don't have as much experience with micro servos.
The metal gear micro servo I've used has different splines than the plastic gear micro servos.
It's not too hard to attach wheels to servo horns. [This thread shows several examples of attaching wheels to servos. The first page of the thread shows a Lego wheel attached to a servo horn and the second page shows a Vex wheel attached to a servo (without using the horn).
I think it's easier to attach wheels or gears to metal gear servos than it is to attach things to plastic gear servos because metal gear servos have a nice tapped hole for the a machine screw on its output shaft.
The original motors you purchased didn't have a gearbox. It's very unusual for a DC motor to have enough torque to propel a robot without a gearbox.
Pololu sells all sorts of nice little motors. They sell some without a gearbox but these are intended to be as replacements to be used with a gearbox. IMO, you shouldn't purchase motors to power a robot unless the motor includes a gearbox.
Oldsteve's strategy of purchasing a combination of wheel with gearmotor is a good one unless you know how to adapt wheels to various output shafts. It's harder than one would first expect to attach a wheel to a motor not specifically designed to fit on the motor.](http://forums.parallax.com/discussion/145826/cheap-bot-a-possible-bsa-robotics-merit-badge-robot/p1)