How do window size, sample rate influence FFT pitch estimation?
Use a Gaussian window - the Fourier transform of a Gaussian is a Gaussian
Log-scale the spectrum to emphasize peaks and turn the Gaussian peaks into parabolic peaks
Use parabolic interpolation to find the true peaks.



  Note that, as mentioned in §D.1, the Gaussian window transform magnitude is precisely a parabola on a dB scale. As a result, quadratic spectral peak interpolation is exact under the Gaussian window. Of course, we must somehow remove the infinitely long tails of the Gaussian window in practice, but this does not cause much deviation from a parabola, as shown in Fig.3.30.


https://ccrma.stanford.edu/~jos/sasp/Quadratic_Interpolation_Spectral_Peaks.html



I estimate 1000.000004 Hz for a 1000 Hz waveform this way: https://gist.github.com/255291#file_parabolic.py

If you're having trouble, plot the spectrum and use your eyes to see why it's not working.