Power Problem USB vs. Battery Power

I am having a strange problem and need guidance on what may be causing this. I have a project powered by an Arduino Mega; when I supply power via USB from my computer, it works great (even my very old Mac which I believe has lower voltage USB). When I power via battery through DC barrel jack, the LCD is hard to read and the ping sensors don't operate properly. Clearly there is a power issue, but I don't know what or why. For batteries, I am using fresh AA's in a 6 x AA = 9v which is well within the input range listed for the Mega. (I've also tried a single 9v battery through the DC barrel jack, same bad result).

I am using completely separate power supplies for the rest of the project...I run a separate supply to the Adafruit Motor Shield, and a third power supply to power the servo (common ground on that one).

Any suggestions??

Actually measure the voltage going into the Arduino when the battery is connected and under load.

Grumpy_Mike -- I am measuring 9.12 volts. I wasn't positive where to measure, please let me know if this isn't the correct method: I popped the top off of the barrel jack connector so I could connect my multimeter problems to the +/- terminals. I assume anywhere I measure on the Arduino will give me 5v regulated voltage?

OK so it looks like your voltage is holding up.
Now try some extra decoupling capacitors around your sensor. Large ones like 47uF close to them.

You can also try a 1K pull up on the RX pin.

Is there a good connection at the Barrel Jack?

Edit in response to @Grumpy_MIke's comment in the next post ....

My question relates to whether the power plug and the Arduino socket make a good connection with each other. There are several different versions of concentric power connectors - some are for very fat centre pins and others for thin centre pins so there may be a mismatch. Also, in my experience they can suffer from corrosion when unused for a while.

...R

I think he means unscrew the cover of the plug that fits into it.