I have the same issue. Brand new Mega2560, Ubuntu, IDE 0021. The strange is that when I change the speed of serial monitor to 57600, the board is sending "Reset" message continuously, every 4-5 second. The board is alive, the green led is on, but when I try to upload the bare minimum sketch I get this: avrdude STK500_2 RecieveMessage (): Timeout.
The board type and USB port are selected correctly. Recently I see a lot of such issues over many different forums. Please help!