Thanks for all the help guys. Looks like my problem was simply power issues all along. Plugged a wall wart into the 2560 with the tranmitter hooked up, the uno into my computers USB with the receiver hooked up and walla, hello in hex is coming through.
Stupid batteries =p That does not bode well for me planning to use batteries in the devices that will be doing the transmitting!
EDIT:
Well it's mostly working. Even with a 13cm piece of wire plugged into them for an antenna I can't separate them more than a couple inches without loosing all the data.
Guess that is a sign that I have a lot of interference in this area or something.