The ONLY way forward is for cryptography to become more widely understood. People will only truly trust Bitcoin once they get comfortable with the idea of keypairs and how message signing works. Until then, they will be uneasy about it.
Yesterday at the meeting of our local Bitcoin group we had a guest who more or less said exactly the same: for somebody who doesn't understand much about computers, let alone cryptography, Bitcoin is just as opaque as our current monetary system. To them it boils down to replacing bankers with geeks and that's not something many feel very comfortable about
I think it is time for a follow-up to the "What is Bitcoin" video - maybe a "How does Bitcoin work"...
It should make the basic principles of Bitcoin accessible to the non-technical audience and it should do so in a way that does not oversimplify things. It doesn't hurt if it is a bit longer (~10 minutes), but it should give everybody the feeling that they understand Bitcoin and that they can really trust it.