L293D Motorshield Perhaps not supplying enough power to motors?

The L293D is very inefficient and is likely to be dropping 2-3V so you're probably getting no more than 3V across the motors. You really need to be powering it with at least 6V, preferably more.

steve