When you burn the bootloader and get the verification error, did you try to upload a sketch anyways?
The Arduino Mega2560 bootloader through the Arduino IDE gives a verification error that does not affect the burnt bootloader. I have manually verified the .hex bootloader file with AVRDUDE and received no verification errors. Something else is confusing the Arduino IDE.
Also, remember that if you burn a sketch through the ICSP (500 ISP clone), the bootloader is overwritten and the Atmega8u2 will no longer be able to upload to the Atmega2560. To turn the Mega USB upload back on requires a bootloader on the Mega2560.