First, for your particular application, you really only need 1 kHz or so sampling rate, assuming you're tuning the fundamental frequency and not one of the inharmonic partials...
Anyway, as for the maximum possible sampling rate, the Arduino manual says:
It takes about 100 microseconds (0.0001 s) to read an analog input, so the maximum reading rate is about 10,000 times a second.
This would imply 10 kHz sampling frequency is the max. However. You can get higher sampling rates by accessing the ADC registers directly. The Arduino Realtime Audio Processing page uses two channels at 15 kHz, for instance. So the 10 kHz max is only while using the built-in AnalogRead() function, because it has a lot of overhead.
The ADC is optimized for best operation with a clock speed of between 50 kHz and 200 kHz:
By default, the successive approximation circuitry requires an input clock frequency [ADC clock] between 50 kHz and 200 kHz to get maximum resolution.
Since an ADC conversion takes 13 clock cycles, this would be a sampling rate of 4 kHz to 15 kHz. According to AVR120: Characterization and Calibration of the ADC on an AVR:
For optimum performance, the ADC clock should not exceed 200 kHz. However, frequencies up to 1 MHz do not reduce the ADC resolution significantly.
Operating the ADC with frequencies greater than 1 MHz is not characterized.
1 MHz clock frequency = 77 kHz sampling frequency, so that's the realistic max.
The forum thread Faster Analog Read? has more about this.