Arduino uno + XBee Shield Not transmitting when under battery power?
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.