The sentence "a qubit is both 0 and 1 at the same time" is everywhere, and it hides the interesting part. Here is a slightly more careful version.
A qubit's state is a pair of complex numbers, the amplitudes: a|0> + b|1>, with |a|² + |b|² = 1. When you measure, you get 0 with probability |a|² and 1 with probability |b|². You always get one classical bit out. Nothing is read out "both".
Where the power comes from, if it comes from anywhere: amplitudes can be negative or complex, so they can cancel. A quantum algorithm is a way to arrange the computation so that the amplitudes of wrong answers cancel and the amplitudes of right answers add up. That is interference, not parallel universes doing your homework.
Two more things that get blurred:
nqubits have2^namplitudes, but a measurement gives younbits. You cannot read out the whole state, so "it stores exponentially much information" is misleading.- Most problems have no known quantum speed-up. The ones that do are special, and the speed-up is usually not "instant".
I am not a pessimist. I just think the field is interesting enough without the slogans.