Originally, I thought that the motors were drawing too much current and causing the supply to trip out. But, I've upped the supply to a 1.5A unit and the problem still happens when the motors don't have any load. Also, if I power the Arduino from a separate power supply (i.e. USB) this problem goes away.
That may still yet be the problem. What voltage are the motors being run at? If they are powered from the arduino +5vdc bus then the current limit is not what the wall wart is rated at but rather the on-board +5vdc voltage regulator which will lower it's +5vdc output voltage if too much current or heat caused by drawing too much current from the regulator.
Lefty