stk500 - not in sync(), protocol error

Hello,
I have just spent time looking through past posts as well as taking time to try all of the suggestions on the troubleshooting page of ardunio.cc.
My problem is that I can no longer upload anything to my Arduino Nano Board (w/ ATmega328). I also have a Arduino Duemilanove (w/ ATmega328) that I first used to program. It installed itself on COM3, and things worked fine with that. I just ordered this Nano, installed on COM4, and the first several times, I was able to program it. I had it hooked up to a breadboard, where I was able to make it light up LEDs on and off, and I used an external power supply a few times and verified that I would still work with that (never did I use both external 5V and USB power at the same time).
Now all of a sudden, when I try to upload programs to the board, I get this trace message:

Binary sketch size: 3980 bytes (of a 14336 byte maximum)
avrdude: stk500_getsync(): not in sync: resp=0x00
avrdude: stk500_disable(): protocol error, expect=0x14, resp=0x51

Just to make sure, I went back to using the Duemilanove, and that still works, and I can program with no problems. I even restarted the computer the first time to make sure that a loaded driver was not an issue.
I have seen a similar post to this problem, but in that thread, the people seemed to fix the issue themselves, so there was no real tied up loose ends.
One of the things I read was that the bootloader might be not installed. When I first power up the Nano, I do not see the little yellow light (connected to Pin 13) light up anymore, and I feel like I did see that before. When I tried to burn a bootloader (I tried several), I got the same message as above.
I make sure that I indeed select COM4 for the Nano, but it refuses to load.

Are there any suggestions?

Using your other working arduino as a programmer with 'ArduinoISP' didn't work?

I got this when i used an ultrasound sensor in my project which is connected on the rx/tx pins. After disconnecting it for the upload it worked. You did not write if there was anything connected at the time of the upload. Maybe this helps?