I currently have code for an FHT but I need it to be able to identify changes as small as 4Hz.
Following another forum post I have changed my ADSCRA to 0xe7 but this gives the frequency to the nearest 37Hz and having read up on the ADSCRA function I realised that this is the best it can do. I need it to be as accurate as possible between 70-400Hz.

I don’t mind if it takes longer to process, I just need a higher resolution.

void setup(){
Serial.begin(115200);
ADCSRA = 0xe7; // set the adc to free running mode
ADMUX = 0x41; // use adc1
DIDR1 = 0x01;
}

void loop(){
for (int i = 0 ; i < FHT_N ; i++) { // save 256 samples
while(!(ADCSRA & 0x10)); // wait for adc to be ready
ADCSRA = 0xf7; // restart adc
byte m = ADCL; // fetch adc data
byte j = ADCH;
int q = (j << 8) | m; // form into an int
q -= 0x0200; // form into a signed int
q <<= 6; // form into a 16b signed int
fht_input[i] = q; // put real data into bins
}
fht_window(); // window the data for better frequency response
fht_reorder(); // reorder the data before doing the fht
fht_run(); // process the data in the fht
fht_mag_log(); // take the output of the fht
binSelect();
detect();
}

Yep, sample rate has to be at least twice the highest frequency. Poisson distribution or Nquist distribution or something, certainly one of the distributions (it's been a while).

My FHT does work, It's just changing the sampling rate which I'm having trouble with because the ADCSRA function has a resolution of 37Hz at it's best.

to sample slower, you can either setup the ADC to sample on a slower interrupt, or just use analogRead(). the latter is probably easier to get started with. you can call analogRead(), and then put a delay in for the right amount of time. be sure to comment out all the ADC setup code before using analogRead().

You can try parabolic interpolation. The theory is that the continuous Fourier transform of the input signal looks like a parabola near a peak; the practice is to locate a peak among three adjacent frequency bins, fit a parabola to the magnitudes at those bins, and estimate the location of the vertex. Here's a link that describes how to do it: Peak Detection (Steps 3 and 4).

Alternatively, you could give up on the digital Fourier transform, and use autocorrelation instead. Here's a scholarly paper that describes autocorrelation and the YIN algorithm for frequency estimation: http://www.ircam.fr/pcm/cheveign/pss/2002_JASA_YIN.pdf.