With the version of avrdude that comes with Arduino 1.0, can you try using the "wiring" programmer type instead of "stk500v2"? That is, change the Mega 2560 entry in the boards.txt file. Does that solve the problem too?
There's a Google Code issue for this, too, that would be a good place to keep track of the problem: Google Code Archive - Long-term storage for Google Code Project Hosting.