If you don’t mind, let me know after you try the replacement of the two avrdude files with the older 0023 versions and if that indeed got your Mega2560 reliably uploading again…
If this fix works for a number of people, I was thinking about requesting it be added to the “Why I can’t upload programs to the Arduino board” section of the Arduino Troubleshooting post on this board. Since this appears to be a IDE 1.0 or later problem, it may help many without having to post as I missed the post tgiving the solution to my Mega2560 upload problem in my early look. I did consult the posted trobleshooting guide as that is nicely at the top of forum board.
Hopefully a permanent fix can be included in later IDE versions if that is possible. Sounds like the issue has to due with >= 1.0 using the standard version of avrdude now and the STK500v2 proto the Mega2560 uses. I’m not an expert on the Aruino of AVR environment yet as this was my first use of an Arduino. I also am going to try the boards.txt change that mellis suggested based on a Google post since I jumped on the avrdude file changes to 0023 version first.
Anyway, good luck and I hope it fixes your problem too!