I don't think it's the bootloader. To recover from my most recent test I swapped the ATmega328P from my Uno and put it into my Duemilanove. I switched the "Serial Port" to /dev/ttyUSB0 but had to leave the board type as "Uno" or uploading would not work -- I figured this was because the ATmega328P had optiboot on it.
After that, I was able to reprogram the chip easily even though it had the tight serial loop code / optiboot.
@Senso: pressing reset doesn't really help. I tried varying my button push timing systematically (then randomly) and coudn't come up with a reliable procedure that I could say with certainty was responsible for the success of the upload, though I did get it to work once (but not with the example program in the OP of this thread).