The important thing to realise is that time-stretching audio works in a fundamentally different way from video slow-motion. For video, it's really simple: you just record at a higher frame-rate and slow that down to something more usual.
If you apply the same technique to ordinary audio, what you get is not just slower, it is in particular also lower in pitch, because the frequencies themselves are slowed down (lower pitch simply means, the oscillations are slower). The well-known chipmunk effect was originally created by just speeding up tape tracks. If you just slow down, you get a cheesy monster-voice kind of effect.
Modern software avoids this, roughly speaking, by splitting up the audio into its frequency components for each time1, slowing down the stream of these frequency coefficients, and transforming that back. Trouble is, “frequency at a given time” isn't really well-defined: you have to give the signal some time to “swing”, to be able to measure frequency at all. The longer you make these time windows, the more accurate the frequency spectrum will be, but at the same time you're losing the time resolution, and that's what you particularly need for strong slow-downs.
It's a nontrivial tradeoff. Time-stretch algorithms basically have to guess what the “real” evolution of the spectrum would be – there is no way to determine it exactly. Hence strong slowmo audio sounds so synthetic: is is synthetic; the algorithm has to guess/synthesize information that isn't really in the recorded signal. This has nothing to do with the sample rate, just with the physics of audio as such.
Some algorithms can actually do 50× slow down without sounding obviously artificial, but this really just means they are particularly clever at synthesizing the inferred part in a way that fits in “naturally” with the real sound components. It's still synthesized though.
1Incidentally, you could say the same happens also in video, and well before the signal is even digitalised: the camera sensor of a colour camera separates different frequencies of light – that's just what colours are! – and stores only the information about the amplitude of each frequency component, rather than recording the light waves as such. Light waves oscillate much, much faster than audible sound (hundreds of terahertz), therefore its no problem do make the time-windows very short, like a microsecond. For sound, the absolute minimum length of a time window is the reciprocal of the highest audible frequency, i.e. 1/20 millisecond; in practise, you have to make it much longer to actually get any useful frequency resolution.