Authentication is hard. It's not a new problem at all. You can go to a great deal of trouble performing secure key distribution, but if you don't have a way of knowing you're doing it with who you think you're doing it with, you're basically screwed.
PGP is nice in that it bundles key distribution together with authentication, so you can at least be sure that the person you spoke to first is the same person you're speaking to now, assuming nobody's taken a $5 wrench to their knees. Unfortunately, PGP and all other factoring based key distribution methods are only secure for a limited time. People often say things like, "Secure for 1000 years assuming..." What they don't tell you is those assumptions (e.g. crackers only use classical computers with Moore's law scaling resources and currently known algorithms") are ridiculous. In general, advances in algorithms alone accelerate things greatly. Messages you send in PGP today will probably be trivial to crack within a decade, and that's not even accounting for quantum computing! Note: If you are interesting enough, this translates to messages you send today will be logged, archived, and cracked within 10 years. This is fine for credit card transactions. Not so fine for government secrets. (If you ever hear of a government employee transmitting state secrets using PGP, you are well justified to freak out.)
Quantum Cryptography promises to at least get rid of that problem, since the impossibility of cloning quantum information means that keys cannot be archived and cracked at a later time. However, authentication with a party you have not physically met remains a bit of a pickle.