Signal to the audio jack of a smart phone
Providing the phones audio circuitry has the bandwidth/sample rate to deal with > 15.625kHz, and assuming your frequency detection code is okay, then detecting tones this far apart should be no problem whatsoever. There are plenty of code snippets and the theory behind them around the 'net if you look around a bit. A good place to start your search for code would be touch tone (DTMF) firmware, theory wise look for stuff like correlation and FFT.   

Make sure you confirm the bandwidth of your particular phone, you may need to reduce the frequencies involved if this is a possibility for your project.

There is a good introductory example of a simple DTMF detection technique from Olin in this question. Any decent DSP book will have plenty more on the subject.