Duemilanove chip in Uno Board?

It should be fine as is, but I think the Optiboot loader is smaller and possibly faster than the Duemilanove one.

If you have more than one board, you can use one to program the bootloader on the other, as I describe here: