I'm using a block 9V battery powering two of these motors:
At first I thought that the 9V battery wasn't enough for both the motors and the bluetooth shield so I bought a dc jack so I could plug another 9V battery to the arduino but the problem persisted. The thing is even without a battery (only using the usb port to power it) the motors run fine (a bit slower, of course) and I can send the input through bluetooth.