Are you just stacking the shields on top of one another? If the two shields use the same arduino I/O pins, this won't work, you can't use the same pin to talk to 2 different shields at once.
If I use Duemilanove, stack XBee Shield above it, then plug in Xbee, the Xbee can sned and receive data correctly.
If add the Ethernet shield between Duemilanove and XBee Shield, the XBee doesn't work as expected.
So I think the code and the XBee configuration is correct. The only difference between the correct and incorrect behaviors is the exist of the Ethernet shield.
I think there's a basic issue here. The Arduino has a certain number of I/O pins. Each pin can only do one thing at a time. If you have just the xBee shield, everything is fine. But if you have two shields, you have to make sure than no Arduino pin is connected to anything by both shields at once. So, for example, if both shields use the Arduino D1 pin for something, they can't work together - there's no way for the Arduino to differentiate which shield is using that pin. Worse, even if one of the shields doesn't use the pin, but just has it connected to something (ground for instance), it still won't work, as the other shield "assumes" that the pin isn't connected to anything else. So even if you aren't trying to use the Ethernet shield, its presence can screw up the xBee shield, as some pins may be shorted, grounded, etc.
The only way you can stack 2 shields is if you can be certain that none of the pins used by one are used by the other, and vice-versa.