Did you get the arduino tx, rx lights? That's the test if it got onto the board. If you got the lights, well, I may have just run out of ideas. Could there be some voltage shift thingie going on? I know I had trouble going from 5v to 3v and so forth for a while, but it doesn't sound like this is your problem. There is also the possibility that the xbees are starving for voltage when they try to transmit. That will shut them off sometimes and the period is short so it may not show up on a voltmeter. If this is the problem you need a capacitor to buffer the supply voltage for them. Hmm, let's see if I can think of anything else...
I know, try one arduino at a time shorting the far end xbee so it sends back the character. That could help localize the problem since the arduinos work wire to wire and the xbees work rf to rf. Try isolating one wire to rf link at a time. I don't know if this will help, but maybe something will turn up by trying. If you have rssi leds on the xbees you should see them go on when the character comes in. If you don't, prowl in your boxes and get one out, they can be hooked directly for the short term and you don't have to search for a resistor as well. At least the rssi works like that on series 2, I haven't tried series 1 this way.
Heck, you may have to get a voltmeter and look for pulses on the darn arduino digital pins to see where the signal is getting lost. It's out there somewhere.....isn't it?