Hard to say without more diagnostics. After all, in the case of my robot car, something that should have worked perfectly in theory was just showing very low voltages on the oscilloscope. Hence I had to add a buffer chip. So sometimes just hearing a description of the problem doesn't help.
However a solitary 0 (as I surmise is happening) could be caused by attempting to read from the serial port before things have stabilized (eg. one part has "come online" before another). I think a short delay, before opening the serial port, might help.
Nice catch! Adding a simple delay(500) right before opening the serial port did the trick! I now get garbage-free data!

Thanks for all the help Jack and Nick, and sorry you had to pull out all the equipment right before we solved the issue

This was a great learning experience. You can really count on this community for help. Hopefully, in the future, I can provide someone else with the same dedication you guys gave my problem.
Just for third-party reference the two problems I was having were:
1. The garbage byte ð or y the after you initiate serial.
a. to fix this you add a small delay(500) before you initiate serial (Serial.begin(x)).
2. Incorrect/improper baud rates
b. Fixed this by changing the baud rate of the XBees in a terminal client ATBD1B207 and also changing it in the arduino sketch (111,111). Serial port still reads it fine at (115,200).
Cheers,
-Francisco