The newer Duemilanove boards, at least the ones from makershed, have the *328 installed at no extra cost. I just yesterday picked up one, and it is labeled *850. Otherwise they are the same.
30720 bytes of program space available.
[edit]
Also to note: Around the holidays makershed had the Duemilanove available in a rainbow of colors, and then it sold out for awhile. The newer 850 series Duemilanove with the 328 installed appeared very recently from the void the older model left. No price increase noted, but the new one is only available in one color. 
[/edit]