Edit: skip to the bottom for a decent solution.
By default, analogRead() is far to slow to properly sample signals at 1kHz+. There are several things you can/should do if you want to use the Arduino ADC for tone detection:
Change the ADC clock prescaler. At 16MHz, I've been able to set ADPS as low as 3, although accuracy will be reduced.
Stop using analogRead(), and write your own ADC read wrapper. There is a lot of cruft in analogRead() that you don't need if you know what you're doing.
Put the ADC in free-running mode, so you don't have to wait for it to sample.
By doing all these things, it's possible to bring the sample rate of the ADC close to 10kHz or beyond, which is fast enough for your purposes. Note that unless your are quite clever with your code, this process is likely to use up almost all your cycles, leaving you with a not very useful Arduino.
However, there's an alternative: good ol' analog filters. Build two peak filters with high Q at your frequencies of interest, run them both into peak detectors, and then your Arduino need only look at two digital signals.
Edit: another way to do it. Rectify the audio, and clip it to a digital signal. Then count pulses in a constant time interval with the Arduino. This is the easiest way to do things (least hardware, doesn't require too many cycles, can run in an interrupt).