Help needed with baud rate

Hello i have a arduino duemilanove with a arduinoXbee v1.1 shield and a bluetooth bee.

If i use the standard sketch and redifine my rxd and txd port i get the green led blinking and the red led blinking.
I can even connect with my pc.
But if i want to use my android phone i need to set the baudrate too 57600.
If i change baudrate 38400 too 57600 i only get the green led blinking.
I tried 20 sites to fix the problem but everytime it works with 38400 but not 57600 or any other baudrate.
Even the second demo sketch doesn’t work.
What am i missing?

Only sketch i get working:

I have the same problem!