Arduino Restarts on Motor Direction Change

I have an interesting problem that seemed to develop out of nowhere. I am using an Arduino Mega 2560 and DFRobot 1A Motor Shield (here: http://www.robotshop.com/dfrobot-arduino-compatiable-motor-shield.html) to run a small, 4WD robot (this kit: http://www.robotshop.com/DFRobot-4WD-Arduino-Compatible-Platform-wEncoders-2.html). The problem arises whenever I try and change the direction of the two motors on one side when both sides have been running. To get a picture of what I'm doing, here is a simple program that causes the problem:

void setup() { 
  pinMode(6, OUTPUT);
  pinMode(7, OUTPUT);
  pinMode(5, OUTPUT);
  pinMode(4, OUTPUT);
  delay(3000);
}

void loop() {
  digitalWrite(4, HIGH);
  digitalWrite(7, HIGH);
  digitalWrite(5, HIGH);
  digitalWrite(6, HIGH);
  delay(500);
  digitalWrite(5, LOW);
  digitalWrite(6, LOW);
  delay(2000);
  digitalWrite(4, LOW);
  digitalWrite(7, LOW);
  digitalWrite(5, HIGH);
  digitalWrite(6, HIGH);
  delay(500);
  digitalWrite(5, LOW);
  digitalWrite(6, LOW);
  delay(2000);
}

Pins 5 and 4 run the left side motor speed and direction, respectively, and 6 and 7 run the right side. This code runs both sides forward for half a second. Stops them for 2s, then does the same thing backwards, then repeats. The problem arises inconsistently at different points. Most of the time, the motors will run forward, wait 2 seconds, run backwards, wait two seconds, and then stall immediately when starting to move forward again, causing the arduino to restart (L blinks twice, then sketch restarts). Interestingly, when the sketch restarts, oftentimes the motors will stall on the first move forward. This will happen several times (a varying amount), and then randomly work again (on, say, the fifth attempt) for one forward-back cycle.

The robot worked fine for weeks, and this problem just cropped up a few days ago. I did not change any wiring between when it worked and when it didn't, and sketches that worked fine previously (such as the one above), now do not. I tried decoupling the motors, and with them decoupled the robot sometimes does two forward-back cycles on the initial startup, but otherwise the behavior is exactly the same.

Any help on what the problem could be, or what I could try to fix it, would be greatly appreciated. I have another motor shield (the 2A version of the same), and the problems are the same on both, suggesting it is not the motor shield. I do not think it is solely the motors, as they work fine forward, backward, and switching if I run them independently. Furthermore, the problem still exists even if I add delay between setting the motor direction, and telling them to move.

EDIT: I forgot to add this when I posted, but the robot and all sketches will work fine under USB power. This only occurs when running off the battery.

Thanks.

Are you using a single battery for both Arduino and motors? If so, consider using two batteries, one for the Arduino and another for the motors. This is the way many small robots are set up, with a separate large-capacity battery for the motor(s). Power glitches due to the motors current are quite likely to crash and restart the Arduino if they're both on the same battery.

Use more supply decoupling. That will prevent it happening.

Thanks guys, it seems to be a combination of bad batteries and running the motors and arduino off the same power supply (thanks for the tip, anachrocomputer). I'll fix the wiring and hopefully it will work then.

Any project using motors should contain some decoupling. The motors should have reverse bias protection diodes and probably a capacitor across the motor contacts as close to the motor as possible.
http://www.thebox.myzen.co.uk/Tutorial/De-coupling.html

http://www.thebox.myzen.co.uk/Workshop/Motors_1.html
http://www.thebox.myzen.co.uk/Workshop/Motors_2.html

http://aedownloads.com/pdf/solder_caps.pdf