Sounds like a bad connection between the board and the computer. Is this an Arduino NG? It's possible that something came loose on the board in shipping – sometimes working, sometimes not. Maybe you can get it replaced?
One thing you can try to get a bit more information is changing
upload.verbose from false to true in your Arduino preferences file (
http://www.arduino.cc/en/Hacking/Preferences). It will dump every byte of data going between the computer and the board. But a flaky connection is a flaky connection, so I'm not sure it will help to know exactly which byte is wrong.