While 8 kHz is low if you look at the carrier of the speech signal, which is something like the pitch of the speech, it is pretty high compared to the envelope frequency of the speech signal. You do not move your jaw, tounge and lips at anywhere near 8000 times per second. The algorithm looks at things like how the jaw, tounge and lips move during speech, and I guess 8 kHz is quite enough for those.
I've never had poor cell phone reception change the frequency of the sound, only silence, choppiness, or complete garbage being inserted - all of which should be detectable via typical DSP algos.
That's pretty amazing if they can detect it within the poor 8khz of a phone. I wonder how awful cell phone reception changes the accuracy.