Arduino Uno and Xbee - why won't they communicate?

This appears to be the documentation I think:
http://itead-europe.com/pm/platform/shield/xbee%20shield/DS_IM120417004_XBeeShield.pdf

Since you use SoftwareSerial did you notice this section in the documentation?

... When XBee communicate to Arduino software serial ports, set the jumper connect DIN to
D2~13, DOUT to D2~D13 by the setting from the code ...