I just changed the chip for 3 of my boards. But I have the same problem with you. I have Sparkfun AVR Pocket programmer. But it doesn't work. If you already know how to do this, please let me know.
Finally I've got it to work. Actually the error I saw was okay. I saw this error after
I tried to program bootloader from Arduino 022:
avrdude: verification error, first mismatch at byte 0x3e000
0x0d != 0xff
avrdude: verification error; content mismatch
But from this URL: http://www.cbxdragbike.com/arduino/bootloaderdocs/index.html
Actually the above error is normal. And I programmed the 3 boards to work fine now.
You'll need Sparkfun AVR Pocket programmer with Arduino. That's all.
You just choose 2560 from board. Then 'Burn bootloader'..
In the end, you'll see the error message that I posted above.
But in fact, it works fine. I programmed all 3 boards with the latest firmware.
I used the hex file that you mentioned (stk500boot_v2_mega2560.hex).
At first, I tried to program with my Olimex AVR Programmer. I could program the boards with AVR Studio but then I ran into Fuses setting problem. So from there, I tried many fuse setting combination. I even downloaded the bootloader code and compile. The hex file size that I compiled is only 8KB comparing to 20+KB for stk500boot_v2_mega2560.hex.. But still, I ran into fuse setting problem.
In the end, I gave up the fuse combination thing and gave Sparkfun AVR programmer a try. And it showed an error message in my second message above. Then I found that the error message is normal. So I tried to program APM 2.21. And it worked just by chance.
i was wondering if you might share where you can find the chip. or do you have a part number.
I am in the UK so I used RS but digikey or farnell in the US should have them its an Atmel ATMEGA2560-16AU. You should find them easily or try google.
thank you very much.