ATmega168 /ATmega328

Can I simply replace the 168 in my duemillenove with the 328 chip

Yes. Make sure it has the bootloader on it.

Bootloader and don't forget to select the "Duemillenove w/ ATmega328" in the board drop down.