avrdude: content mismatch - tried everything!

I received your official starter kit from my wife (via Amazon via Canakit) for xmas and immediately started working through the exercises. I am using Ubuntu Linux 12.04 LTS, Arduino IDE 1.0.5, and an UNO rev3 board. I ran through the first 2 exercises no problems. I then build project 3 'Love-o-Meter' from the book which uses the temperature sensor and the serial console. Everything was working great that evening. I put the breadboard/uno into a box for the night. The next morning I tried to put the device in my daughters room to measure ambient temp but for some reason its not working. I try to re-upload the Love-o-Meter code but now I get the following error:

avrdude: verification error, first mismatch at byte 0x0000
0x0c != 0x00
avrdude: verification error; content mismatch

Then I tried a few things:

  1. Ok, so I attempt to upload the basic 'Blink' example to the board with everything disconnected, Same error!
  2. Swapped out USB cable - Same error
  3. Use a different Linux host computer for IDE - Same error
  4. Try to upload code from a Windows host - Same error
  5. I try the reset process - hold reset button, remove power, re-apply power while holding reset for three seconds - same error!
  6. I ran through the loopback test described in this form and everything checked out as well.

I am at my wit's end here. Do I have a defective board or what else can I try? I already stuck the breadboard onto the wooden backing, so I don't know if I can return it anymore either. Please help so I can make some cool toys for my daughter! Thanks.

As a followup, I turned up verbosity in the IDE to see what command was being run. Here is a pastebin link to the complete output:

Any help would be appreciated.