1. Quantum computers are powerful because they act in many universes at once
This is an oversimplification based on the MWI at best. I don't think it has any pedagogical value. It needs to stop being repeated. Every journalist I talk to asks whether it is a good thing to write. I always say no.
2. Quantum computers/physics is weird and random
Anyone not swept up in the parallel universes seems to think that quantum computers are just some weird random thing. As before, there is a kernel of truth, but it is not a good explanation. Quantum algorithms are all about managing the certainty in the system, moving it through the state space to turn a certain input into an (ideally) certain output. The randomness is there, but I don't think it should be the focus of an understanding of quantum computing.
There seems to be an idea that quantum physics is just a strange random thing. And so quantum computers are just computers with weird randomness going on. From what I've seen, anyone who doesn't get swept up in the whole 'computing in many
3. Quantum physics does not follow logic
The popular talk of how strange and weird quantum physics is makes it seem quite illogical. This is pretty bad from the perspective of quantum computing, since computers are build on logic. How can a programmer be expected to make the move o quantum if they think that quantum programming is illogical? If the quantum world seems like a mystical realm understood only through arcane knowledge, it will be hard to engage people outside of the field.
Though quantum physics doesn't follow the logic of local hidden variables and non-contextuality, it of course has its own logic. The fun of quantum computing is learning how to embrace and use effects that are not possible in classical variables.
I think we should be championing the message that quantum computers are full of logic and certainty, and that these are what we harness to do computation. Too much talk of random and strange effects should be avoided. As should the whole multiple universe thing.