Maximum sample rate of Arduino Duemilanove?
I don't think you can sample that fast at full resolution. The ATMega168 can only sample at 15 ksps at its full resolution.

Having said that, you should be able to get a suitable sample rate to get a functioning guitar tuner. 44.1 kHz is most likely a fair bit faster than you will need given that the fundamental of the high E string an a guitar is around 330 Hz.