I fixed my problem. Arduino is apparently VERY picky when it comes to the cross-compile environment.
If you use GCC < 4.4, you cannot program for the Arduino Mega 2560. If you use GCC 4.4 <= ver < 4.6.2, you get that serial issue. Only 4.6.2 works as far as I have been able to find (I tried a lot of combinations!)
Additionally, libc MUST be version 1.7.1. Version 1.8.0 deprecates some functions that arduino uses. Binutils needed to be 2.21.1-r1 (2.22 didn't work for some reason).
In Gentoo, this is a solvable problem. Somebody else posted the same solution, and it's the same solution I somewhat-independantly came up with:http://arduino.cc/forum/index.php/topic,93672.0.html
I don't know about ubuntu. Perhaps find those versions of avr-gcc, libc, and binutils in ubuntu?