I've had this problem a number of times. With some luck it is possible to recover by holding the reset switch until the upload starts and then releasing it. This will take several tries to get right. However, the most reliable way is to replace the bootloader. I fought this problem for a solid year before I talked someone into fixing it and providing a bootloader that works.
Take a look at my blog page on the final resolution to this problem at: Desert Home: Arduino Mega2560 - Wrapping up the Bootloader Problem
Funny, the folks at Arduino said they would make this part of the distribution quite some time ago.