If you have Arduino Xbee shield with XBEE Series 2, you should know that actually the module is now called XBee Znet 2.5.
Also the communication protocol has changed between different version. From the manufacturers home page: "The XBee Series 1 and the XBee Series 2 modules have the exact same form factor and are pin-for-pin compatible, but they are based on different chip sets and are running different protocols, so they are not over-the-air compatible".
Luckily I found these instructions from the web: http://blog.didierstevens.com/2009/06/15/quickpost-arduino-xbee-shield-series-2-configuration/ and I was able to continue in my project.
I also run into mysterious "Arduino booting when Xbee was connected" problem. By browsing Arduino Forum I finally found the reason http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1217201592/0or http://rubenlaguna.com/wp/2009/03/05/setting-xbee-to-sleep-causes-arduino-reset/.
However I have not found any good solutions how this problem can be solved. I myself modified my software so that the "coordinator" of the xbee network sends some "Do-Not-Fall-In-Sleep" signals from time to time to other xbee modules in the network.