I don't know the details, but I understand it's possible to select how much program memory is available for the bootloader versus the sketch. I think this is defined by the fuse settings. Is it possible that the board has a bootloader and fuse settings installed that make less space available for the sketch than you have indicated in your boards.txt? I notice that the error occurred on a nice round hex number which is the sort of thing you'd expect if you were just overflowing the space available for storing that sketch.
There was a famous optiboot bug that hit at about that file size (long ago fixed.) http://code.google.com/p/arduino/issues/detail?id=380&can=1&q=optiboot
I don't remember ever hearing about a similar problem in atmegaboot, and it's logic should be different enough that it doesn't have exactly the same error, but it could be related.
You could load up optiboot instead; it is known to be fixed, and is 1.5k shorter as well...
Pretty much all my clone Mega 2560's had this problem. Replacing the bootloader was the fix.
With regards to the bootloader, I'm not sure what the original one was, it just didn't work. Never had the problem on an Uno though ( rare for such a large sketch ). Either way replacing the bootloader can't hurt.