L293D Motorshield Perhaps not supplying enough power to motors?

The L293D is ancient and weak. Use a modern motor driver, like these from Pololu.