XBee not talking to arduino on 38400 or higher???

Hi,
I have 2 series 1 xbees, one is connected to arduino Duemilanove 328 with a XBee Shield remixed http://www.nkcelectronics.com/xbee-shield-remixed.html, and the other is connected to PC with a Xbee explorer. I upload a sketch, all it does is calling Serial.send(10, BYTE). I use X-CTU to check the communication on the PC, and I get the right byte on low baud rates(9600, 19200), but I can't get anything on high baud rates. So I am suspecting something is wrong with the serial...

The Xbees are restored to factory settings with firmware 10cd, I tried to flash lower versions, but XCTU doesn't allow me to do so... The IDE I am using is 0016.

Any ideas?