What kind of XBees are you using? I have the Pros and I had to set one up as a coordinator and the other as a router.
I also have a version of the XBee.h and XBee.cpp that uses NewSoftSerial so you can talk to the computer from your arduino board while communicating with the XBee, really helps to debug.
Matt