You better give up on high sample rates.
See table 28-7 of ATmega328P (duemilanove) for example:
Input bandwidth: 38.5KHz.
Absolute Inaccuracy: 4.5LSB @ 1/16 presample (ADC 1MHz)
There's absolutely no noise induced on USB cable (digital). BUT you might have leaking current to ADC inputs. To overcome that, try the following tips:
- Have a good ground connected on ADC cabling.
- Disable every other ADC input. Also don't use ADC gain (if Mega).
- Despite datasheet saying input impedance is 100M, it is not. I am not sure what's it impedance is. But the idea is to match it on your input (if you have a 1M ohm impedance, make sure your input is also 1M ohm). Also use a stable ADC ref value, this is very very important. If possible, use the internal 1.1V source. Why do I say input impedance is not that high? Simple - connect VCC to ADC input and watch your controller heat a lot. But might be an issue with the muxer only.
I never used a tiny, but should not differ that much. I've a clone actually, but did not use it (yet).
Wondering : if you tie your ADC input to ground, using a 100 ohm resistor, what do you get ? Noise ? And if directly connected to ground ? And if using a 100Kohm ?
Álvaro