What version of it the IDE are you using?
Turn on verbose output in the preferences and paste the results here between code tags.
Keep in mind that the Duemilanove and Mega have very little in common. They use different USB to serial chip, different microcontroller, different bootloader, etc.
Why can't we both get answers on the same page if we both have the same problem?
For reasons I don't understand, "hijacking" occurs more frequently on this forum than any I visit. The "problem" of not being able to program the board is very common. The cause and the
symptoms are usually very different. So posting "I have the exact same problem" leads to the kind of confusion that CB describes.
It's not meant to be hostile. You aren't the first one. Let it go and let's move on to finding your problem.