I receive this same error, but only if I plug an Ethernet shield onto my Mega 2560.
Ie. if I just test out the basic blink example, it uploads and works correctly. If I then unplug the device, add on the Ethernet shield, plug back in, and attempt to upload the same blink sketch, I receive this avrdude errors.
I'm new to Arduino... Are these issues in any way related to everyone else's?