Motor shield R3 does not supply full power
I had a similar project such as yourself, arduino powering 2 motors: I ran into several problems (I Used an HBridge and not the motor shield but you might run into these)

1)My partner and I removed the battery tray housing the 6 AA batteries and instead used 1 9V battery, thinking that was better. It was not, 9V do not provide as much current as AA batteries, it's like using 6 AAAA batteries, google it. You might be better switching to AA batteries b/c once the voltage got low (&lt; 7V) on our project I had to switch it out for a new one, and they didn't last long. Also test that voltage on the motor shield's output terminal screws and compare w/ the voltage across the 9V to confirm it's the same or different (accounting for voltage drop from the various motor shield components, if any).

2)There is an issue w/ the Arduino Uno R2 where it will not run the code correctly if it is being powered via the VIN pin. VERY hard bug to detect.