I am having this exact same problem. I've been using the Mega for about two weeks now, just uploading simple test sketches and such, and suddenly I cannot upload anything and am getting the same error message.
I'm confused as this unit was working today, and now, two hours later, is unresponsive to uploading. I'm working in OSX, so I'm not sure about this being a PC issue. I tried downgrading the arduino software to 1.03, upgrading to 1.05, and none of these seem to work. Not sure how to go about this, but I'm in a similar position as the orignal poster here, where I require the Mega's number of pins, and I have a project that is to go live in about a week and a half.
What other solutions can I try?