Pitch estimation

I'm working on a more sophisticated pitch estimation algorithm. The one used by the violin mod worked, more or less, but was pretty hacky in order to run in real time on an AVR.
Here's a comparison of the two on the same input clip. As you can see, the old one gave a rough-ish estimate of pitch, but very very noisily.
Old algorithm:
pitch_est_old
New algorithm:
pitch_est

The old algorithm took the signal and ran it through complimentary low and high pass filters, and estimated the pitch as the ratio between the (approximated) power levels of the two. The new one is FFT based with interpolation between adjacent frequency bins. It works pretty well except at the lowest and highest frequency bands. Currently I'm just brute forcing this problem by using enough bins that the lowest one is close enough to DC that I don't care. With 128 bands I only need to run about 84,000 real multiplies per second at my sampling rate, so that should work for now.