I have a Fedora 13 system and it came with avc-gcc-4.5.0 and avc-gcc-g++-4.5.0 which for whatever reason break all serial output on the Mega (but not on the Duememilnove). I removed those versions and installed the versions from Fedora 10 and now I can get serial output on my Mega.
This is what is current and working on my Fedora 13 x86_64 system.
avr-libc-1.6.7-2.fc13.noarch
avr-binutils-2.20-2.fc13.x86_64
avr-gcc-c++-4.3.3-2.fc11.x86_64
avrdude-5.10-2.fc13.x86_64
avr-gcc-4.3.3-2.fc11.x86_64
For the record commenting the serial port lines out of Hardware.cpp did not work for me. I had to revert avr-gcc