As a young grad student, I remember going to a talk by Bennett where he explained how a Quantum Computer allows manipulation in a 2^N dimensional hilbert space, while the outputs measurements give you only N bits of information. The trick is to somehow encode the result in the final N bits.

I felt this was a much better layman explanation of what a quantum computer does than simply saying a quantum computer runs all possible paths in parallel.