Without resorting to assembly code or other tricks, I get close to 3000 samples per second for two channels in my LXARDOSCOPE project, available from Sourceforge. The samples from the ADC are transferred through the serial or USB port. The attached screenshot shows a 419.6 Hz sine wave and a 1468.6Hz square wave at a sampling rate of 2938 per second.

Increasing the clock speed is an obvious extension of my project, and I am definitely interested in higher sampling rates for LXARDOSCOPE.
I had a look at your website and ordered am Audio Codec Shield.
At first glance, it is not obvious to me which parts of the test are executed on the ATmega device and which parts with the shield.
My approach is to transfer the samples to the PC in realtime; this may very well be the limitation for higher sampling rates.
When the time comes for digging deeper, we should take the discussion elsewhere.

I think the big unknown is on the PC side: once the data has been received (by the serial or USB port , how long does it take to get into the application program which processes the data on the PC? Since there are many processes running on the PC at the same time, the operating system needs some time to pick up the data and wake up the application program. I think you need to run the time critical part of your application entirely on the Arduino, where you have full control over time.

If you are interested in using FFT for a real world application, have a look at the ATmega328Accuracy project, at http://sourceforge.net/projects/lxardoscope/files/accuracyInvestigation/ . In this project, FFT was used with sinewaves for characterization of the ATmega328 ADC. Results include Signal-to-Noise Ratio and Effective Number of Bits.

For results of an investigation on the accuracy of an ATmega328 ADC, have a look at the ATmega328Accuracy project, located with LXARDOSCOPE at Sourceforge. Some of the results shown are for two channels sampling close to 3kHz. Maybe you can use the preamplifier shown in the report ATmega328Accuracy.pdf for achieving an oscilloscope style input impedance of 1MegOhm as a buffer between the ATmega328 and the circuit you want to measure.

At least for the electrical part of your system you could use LXSNDTEST, available from Sourceforge. The recent versions can interface to an ATmega328. Have a look at the report ATmega328Accuracy.pdf in the LXARDOSCOPE project, also at Sourceforge. The report shows spectra and parametric results like THD, SNR, ENOB.

I present the results of an investigation into the accuracy of the ATmega328 ADC.  I used several circuits in conjunction with the ATmega328; their schematics are shown in the report:
   - preamplifiers with standard 1MOhm||33pF input impedance
   - interface circuit for serial and USB port, with option for electrical insulation.
   - ATmega328 driving a DAC MAX503.
Results for the following tests are included:
   - sinewave test with external source (soundcard),
   - sinewave test with DAC
   - ramp with DAC
Measured results obtained on solderless breadboards:
   - ENOB 9.4
   - Integral Nonlinearity 0.06%
   - Differential Nonlinearity (RMS) 5.6%.
Source code in C and Arduino sketches are included.
The files are located with the LXARDOSCOPE project, available from Sourceforge.

I think the previous comment is in the wrong thread. Otherwise please elaborate how it relates to my oscilloscope project.

Encouraged by the high interest reflected in the number of downloads from Sourceforge, I have enhanced the application, fixed a bunch of bugs, and uploaded the new version lxardoscope_0.85. Please check it out!

Thank you for your comments.
I noticed the following issues on my Mint9 installation:
1. after installing the arduino package (0022+dfsg-1~maverick1) I noticed that my computer took significantly longer to start.
Sometimes an empty window comes up, stays for about 10 seconds, and then disappears. No idea what this is all about, but I do not like it. To program the Arduino, I need this software on only one computer; on all the others LXARDOSCOPE works without it, when using the serial port.
2. with the existing arduinoscope solutions I got about 5 samples per second, and Java was hogging 100% of my CPU. I found on the internet that other people were having the same issues. Replacing the Java software with the SUN version did not help.

Since I had created XOSKOPE (with the soundcard as data acquisition device) it was not too difficult to adapt it to a serial port.
LXARDOSCOPE includes a CH1+CH2 mode, and an X-Y mode (select in Display Mode).
I understand the need to move a way from the serial port. Actually LXARDOSCOPE works just fine with the USB/virtual tty port. However due to the issue mentioned above I stay away from this mode.
LXARDOSCOPE_0.8 definitely has room for improvement; I released this version in the spirit of Sourceforge: release early, release often.

After getting 5 samples per second with Java hogging 100% CPU with an existing solution, I created a new oscilloscope application for Linux. I get close to 3000 samples per second, on two channels. See http://lxardoscope.sourceforge.net
Features:
   - display modes: two channels, time/add/xy
   - vertical: 2mV to 10V per division
   - overall gain control for calibration
   - horizontal: 100us to 5 sec, for full sweep
   - trace position adjustments: vertical and horizontal
   - trigger: on/off, channel 1 or channel2, rising or falling edge
   - trigger level: -10 to +10V
   - signal level measurements: max, min, pp, avg, rms
   - signal levels and time shown for mouse pointer location selected on display
   - up to 3000 samples per second, per channel
   - option for recording input data stream to file
   - option to display recorded data from file
   - timebase calibration adapts to Arduino's conversion speed
   - GND calibration allows for selecting arbitrary GND potential
Screenshot is attached.