XBee baudrate > 38400 corrupt


I'm using a duemillanove (ATMEGA 328) + xbee shield talking to a Sparkfun xbee explorer hooked up to a laptop, using the series 1 xbee modules.

I have tried several times to get a working baud rate > 38400, but I keep getting corrupted data. First I thought that something in my code wasn't right, but now I've recreated the problem with very basic testing code. To be sure I've created one test using Processing and the other using Max, but the results are the same.

I've also tried both types of series 1 modules, with chip and wire antenna, and made sure I've updated them with the latest firmware.

Has anyone ever successfully used a higher baud rate with a 2009 Arduino? Is there any reason why this can't work? :-?