How are you connecting the xbees to the arduino?
The tx of the xbee in question is connected to the rx line of the arduino. I had suspected the problem involved a "feature" of the diecimila board resetting when opening a serial communication at that rate. This seems to have been the case as when loaded to a pro-mini it functioned as intended.
Be aware that if you're using the XBee Shield the DIO7 pin of the XBee is wired to RST in the arduino board. If DIO7 is set to 1-CTS (default) that could easily trigger the reset.
You could read more about this in CTS Flow Control chapter of the Xbee manual.
If CTS flow control is enabled (D7 command) when the serial receive buffer is 17 bytes away from being full, the module de-asserts CTS (sets it high) to signal to the host device to stop sendint serial data. CTS is re-asserted after the serial recive buffer has 34 bytes of space.