Problem with xbees or arduinos?

I'd suggest skipping the xbees first and just get your megas communicating to each other just using wires between the tx/rx/gnd pins. Once you have that working, then introduce the xbees to the setup. This should identify where the problem is.