Arduino uno + XBee Shield Not transmitting when under battery power? I have a few Arduino's along with XBee Shields communicating with one another. 

The problem I'm having is that, when all the Arduinos+XBee Shields are powered via USB(PC) they seem to work fine and all transmissions get through to one another. But, when I use them with 9Volt batteries(fairly new batteries) the whole thing crashes and I never receive responses back from the battery powered ones.

I'm wondering if this is really a power issue? wouldn't a 9volt be enough to power a single arduino(uno)+xbee shield?
Using a multimeter you can confirm your theory by looking for a voltage drop on the power connections to the XBee and into the UNO.

9V batteries don't store much charge, nominally 563mAh according to wikipedia. It is possible that the fairly new batteries are not that new after all.

Depending on the XBee, power consumption varies. 40mA for a normal XBee (ZigBee), 200mA for pro, and 309mA when transmitting for the new XBee WiFi. If the battery is low, the high current draw plus internal battery resistance may drop the 9V output to below the 7V needed for the UNO's voltage regulator to function correctly.