I think your guess about having a hosed bootloader is the most likely cause. Why and how did it get hosed, who knows.
It's a good excuse to get a USBtinyISB programmer kit from Adafruit. It will burn a fresh copy of the bootloader from the Arduino IDE and if your running windows there is now a GUI wrapper for AVRDUDE avalible so you don't have to learn all the command line options and variables to utilize AVRDUDE. This would also allow you to burn in a sketch without having a bootloader resident in memory so you can reclaim that extra memory space for your application.
See, every cloud has a silver lining