I tried out the tutorial on using an UNO to program my mega ADK
I did already mention that ArduinoISP won't program a mega2560... (though I don't think you got that far.)
As it happens, I don't have any m2560 arduinos, and my sense of duty toward community support doesn't quite go as far as going out and paying for hardware that I don't need, in order to debug other peoples' bootloader problems. However, I dug out my mega1280 and tried to upload the "Sprinter" RepRap sketch, which is about 53k. It worked fine.
Now, the mega1280 doesn't have the same bootloader as the mega2560, so that isn't really much of a test. There isn't a .hex file for the new bootloader for the 1280, so I compiled one from scratch using the source in arduino1.0.2 (this only took three tries at avr-gcc versions. Sigh.) I modified boards.txt to create the new board type, "burned bootloader" using ArduinoISP (which DOES work on a m1280!), and uploaded some new sketches. The 53k Sprinter sketch still uploads fine.
This is probably the production bootloader; there's no watchdog support in the source code, and it still has the "!!!" bug. (However, I didn't get a "huh?" response when I added !!! to the sketch. It just never completes upload.)
So I don't know what to tell you. It looks like the bootloader works fine for sketches larger than 30k here. You've repeatedly ignored requests for information from your side (.hex or source code.) I have suspicions that the m2560 doesn't really support 240kbyte sketches, but I'm pretty sure that it should work for sketches larger than 30k. As Nick points out, there have been too many MEGAs sold for a bug this serious to exist (ADKs... Perhaps less so.)
So... please provide your code?
Are you still getting the same "verbose" output with your sample sketch?
Here's something else you can try.
Connect to your Arduino via the serial monitor at 115200bps.
Hit reset on the board, and within 1 second send "!!!" (I have to pre-type the !!! and use two hands for this
This should get you to the bootloader's interactive monitor, which looks like:
!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!
Arduino explorer stk500V2 by MLS
Bootloader>
It has a couple commands, but the one that's interesting is "?" Send a "?", and report the results. My 1280 says:
Bootloader>? CPU stats
Arduino explorer stk500V2 by MLS
Compiled on = Jan 28 2013
CPU Type = ATmega1280
__AVR_ARCH__ = 51
GCC Version = 4.3.3
AVR LibC Ver = 1.6.7
CPU signature= 1E9703
Low fuse = FF
High fuse = D8
Ext fuse = F5
Lock fuse = CF
Bootloader>