Problem with Arduino Uno, L298N and DC Motors

I agree, it's a combination of voltage drop in the L298N and the 9V battery not being able to supply enough current. You need to:

  1. Replace the 9V battery by something more powerful. You could use a bank of AA alkaline or NiMH cells, or a LIPO.

  2. Preferably, instead of the L298N use a modern mosfet-based motor driver, such as this http://www.pololu.com/catalog/product/1213. This will reduce the voltage drop to a small fraction of a volt.