Balancing robot motor issue

I am building a balancing robot based on this

I have it working except when I attach the battery to power it freely the wheels shudder and then spin in only one direction. However when the arduino is powered by the computer it runs perfectly. My guess is that the motors (which are these are getting too much current and cant handle it.

However I am not sure, If anyone can help I am a real noob and this is my first post. Thanks guys!

P.s. I am using the motor shield instead of the one he uses but its the same chip