try to isolate the problem. Hook the XBee to the arduino without using the shield. Use jumpers to get 3.3V ground and the two signal lines without the Shield at all. Don't worry about the voltage difference on the Rx Tx pins, I've done this many times, just don't use the 5V power by mistake.
And, put a delay(1000) in there somewhere to slow it down and not overrun any buffers on any of the chips.
There's a few things that can happen in the configuration of the XBees that can drive you nuts. I've listed the ones that gave me problems on my web page at http://draythomp.blogspot.com/p/world-of-xbee.html. This might help you also.