dougiel:
Have exactly the same problem. Are you using 1.0.1 ? . I was and when I rebuilt the sketch for 0022 the problem went away !. I have no problems uploading to the other boards I have with 1.0.1 only the Mega 2560. Could it possibly be the software ?.
Dougie L
Can you test http://arduino.cc/forum/index.php/topic,118440.0.html ? I upgraded the 'uploader' in that modded version. I had a similar problem (frequently) with 1.0.1 and my 2560 but Samueldw's arduino never worked.