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.