It's also a question of how much resolution is needed. Higher ADC sampling speeds are possible, though at a loss to resolution. Post-sampling data work may also slow the sampling rate down.
Then there is the transfer to your CPU... there may not be enough bandwidth if you have to send a lot of data. The Arduino IDE is limited in terms of its serial bus speeds (no more than 115kbit/s) even though a 16/20MHz Arduino can handle 1Mbit/s transfers w/o errors. If my math is right, at 10,000 samples/s you'd be looking at 160,000 bits/s at a minimum (assuming you don't compress the data) as every sample consists of two bytes of information... then there is overhead, etc. So a 500k or 1Mbit/s connection should be able to do it.
SDFatlib has managed to sample at very high speeds and then make large writes to a SD drive. That's another option.