CrossRoads:
Assume it has no bootloader, and install the Uno bootloader that is included in IDE 1.0.5.
You have a 2nd Arduino? Use Nick Gammon's sketch to bootload the Duemilanove.
Gammon Forum : Electronics : Microprocessors : Atmega bootloader programmer
Type of USB/Serial interface is not material to the bootloader. I bootload all my 328P DIPs as Uno, no matter the actual board I build up around them.
I'm working on the same problem. I have tried installing a bootloader using both the method described in your link and using the Arduino IDE Booloader Burner. Both said the programming was successful but I got the same error when trying to program the Duemilanove afterwards. Is there something you have to do after installing the bootloader before you can program it?