Well - first off, with 5 NiMH cells, you only have 1.2 volts per cell (at approx 2500 mAH) - so 6 volts; this is not really enough to supply proper power to the Arduino via the barrel jack or VIN, both of which go thru the regulator. This regulator (7805 equivalent) is -not- an LDO (low dropout), and so requires a certain amount of voltage over and above its regulation voltage of 5 volts - which is really about 7 volts (7.5 to be sure).
When you plug in the USB - USB provides regulated 5 volts, and this connection bypasses the regulator - thus things work OK. When you use the 9 volt power supply, this is above the 7.5 volts needed by the regulator so it works ok.
First thing to try then would be to use a larger battery. I would go with an 8 cell pack, to give you 9.6 volts. If you need the 6 volts for the motors (likely, given the platform you are using), you'll need to customize the pack to tap off at the 9.6 volts.
An alternative would be to leave the pack as-is, but tap off of 4 cells (for 4.8 volts), and use that to go into the +5V line on the Arduino - which bypasses the regulator (note that you MUST BE CERTAIN OF YOUR POLARITY FOR THE CONNECTIONS - failure to do so will release the Arduino's magic smoke). 4.8 volts is within the voltage level the ATMega can use.
That would be the first thing to try. You shouldn't have any or much problem with signal noise or whatnot from the motors since you aren't using any kind of custom electronics or such; unless the shields and such are poorly designed. If you do suspect noise, you can always add some small noise-suppression capacitors across the motor leads at the base of the motor.
As far as the run-time is concerned - each of those motors draw a max of about 2.8 amps (when stalled); frankly, your h-bridge, which is L298-based - is undersized, depending on how you have the four motors of that platform wired. For these motors, I probably would've gone for one h-bridge (in bridged-mode) per motor to be safe - but you could probably get away with running two motors per board, as long as they weren't both locked up, and you had a good heatsink on the chip (more than the PCB-based sink). Fortunately, the L298 has thermal and current-overload protection...
With those kinds of motor specs - if you split the difference between no-load and stalled on those motors (which I believe are these:
http://www.robotshop.com/dfrobot-6v-180-rpm-micro-dc-geared-motor-with-back-shaft.html), you get about 1.3 amps per motor. I'd say given the mAH of the battery here (2500 mAH - approximately) - you are lucky to get 15 minutes. That pack is kinda undersized.