It turns out that the existing Arduino tool chain (the compiler, linker and so on, but not including AVRDude) also has a bug that prevents it from properly generating code bigger than 128K bytes, which is a problem for the Mega Arduinos.
It looks like both this memory allocation issue and the flash size issue can be resolved by upgrading the Arduino tool chain to the latest. Instructions on how to do that are here:
I have not tried it yet, but its high on my priority list. I'll report back after I try it and run this test.