That's probably happening because the motor's causing a brown out on the Arduino power supply, or causing a lot of noise on the RESET pin of the AVR. Make sure that you've pulled the reset pin to 5V with a smallish resistor (no greater than 10K). Since you're using an Arduino, though, its probably already on the board.
You may be able to confirm this by looking at MCUCSR immediately on reset, ie, right at the beginning of the main() function before you do anything else. You should also be able to see lots of noise on the AVR power supply pins (VCC vs GND), and probably also see the supply level dropping to a much lower voltage than what you'd expect. This is happening because even though you may be using separate supplies, when there's a sudden change the motor's current requirement, it's inductance will draw the power from wherever it can. This means that by the time the current from the separate power supply is available, it'd have dumped a whole lot of noise on the ground, and also pulled power through the IO pin of the atmega which is driving the SN754410, as well as through 5V at the 754410 itself.
The problem is exacerbated by the way in which you're driving the motors and what you're doing to them. By tying the 1,2EN input (pin 1) to 5V, you've ensured that the driver is continuously driving the motor. Each time the motor switches direction, it experiences the worst case condition possible, where it has to go from one extreme to the other extreme. The sudden change in direction of driving and the time the motor will take to respond causes a period during which its going to pump reverse EMF back into the driver and subsequently cause contamination at the ground. Additionally, since the situation is actually worse than a stall, the current consumed is something like 5 times higher than the steady state current required by the motor normally.
In order to fix the problem, there are a few things you can try.
Add diodes on the motor lines to prevent the reverse EMF from reaching the 754410. It'll cause some contamination to the 9V supply and the Ground, but that can be localized to near the motor and not let the AVR see it as much. You should have these in any case. For an example for how this can be done (from the datasheet of the L293, a similar IC), see :
Add heavy decoupling on both the supply lines. Separately decouple the 5V for the AVR and the 5V for the SN754410. Use something like 10uF electrolytic/tantalum with 100nF ceramic in parallel with each, at least. Decouple the 9V supply with something much higher, say 100uF. Try to reduce the contact resistance of the wires bringing in the 9V supply.
- Control 1,2EN from the ATMega as well. When you're changing direction, disable the driver for a short while and let the motor spin down by itself before turning it on in the opposite direction. If you're in a hurry, you could bring the motors speed down to zero slowly and then speed up in the opposite direction, again slowly. You would need a PWM to do this. Avoiding sudden, large changes in speed is a good idea.
- If all else fails, or if you want to use this for a critical application where you care about reliability, don't join the grounds either. Use optoisolation between the ATMega outputs and the SN754410 inputs. Derive the SN754410's 5V supply from the 9V supply in this case using a 7805 or such. This way, any noise you generate there will not effect the AVR's supply.