XBee Pro S1 Baud Rate issues

This is a request for help stemming from this thread: http://arduino.cc/forum/index.php/topic,87639.0.html

I am trying to interface my two XBee Pro S1’s with two Arduino Microcontrollers, but I am having what seems to be baud rate problems.
I updated both of my XBees to 10ED.
I configured the: ID, DL, MY and BD on

XBee 1:
3726, 1234, 5678, 3 consequently.

XBee 2:
3726, 5678, 1234, 3 consequently.

I then tested the communications between both XBees. Everything seems to work.

Connected the XBees to my two Arduino Microcontrollers using Arduino XBee Shields, tried sending Serial data, and this is where it gets tricky. I am getting some garbage bytes on the Serial Monitor/terminal when I transmit Data with a delay between transmissions. Without the Delay, the XBee instead does not transmitt the first byte at all.
I have also tried modifying BD to 4. The same thing happens. At BD > 4, I get no output in the Serial Monitor or terminal.

My guess is there is some misconfiguration with the Baud Rates or something. For more detailed information feel free to ask or see the other thread I have linked.

I have been trying to fix this for days. All help is deeply appreciated.
Thank you for your considerations,

You can contact Digi Technical Support at the following link, http://www.digi.com/support/eservice/login.jsp , digi folks will help you.
If the issue is alredy solved, please update the forum.