Arduin Uno, Wireless Shield v1.1 & XBee2

This one...?

I have a couple of shields in similar configuration; the Seeed Studios, not the Sparkfun.

Are your "Xbees", ZIgbee or standard? I will try to set this up. I suspect that your are not using the "Software Serial" library to move the software to the pins that you are using on the hardware.