I've seen enough arduino starter kits on e-bay and such.
Nearly all of them contained an arduino duemilanove (well, 99% sure they're clones) with an atmega168 chip.
Personally I went for the 328.. they are simliar, if not the same, in price.
The extra program space and memory are worth the difference in anycase.
Might be worth checking which version of the duemilanove the kit contains.