The problem is that, on the whole, users simply don't care. They have more important things to worry about than email encryption (you know, stuff like spouse, kids, mortgage, partying, etc).
The only way I can see end-to-end crypto really being adopted is if it's turned on by default everywhere. The selling point can't be the security, because people don't care about security -- the selling point has to be something else. Anything that requires a manual adoption step is going to automatically limit itself to a very niche audience.
Which is why I proposed that UI: it works automatically. While using the system, it simply indicates to you as you compose the message "Yes, the email address you are sending mail to belongs to the person you intend to message" or "No, that email address belongs to someone else" or "This is a brand new email address." This way when you are emailing your lawyer to set up a will, or you email your accountant with your tax info, you can be sure that (a) you are emailing just the right person and (b) that only they can read the communication.
While setting up the system, you are simply required to link your identity. Twitter, Facebook, LinkedIn, GMail, HN, the government all should allow you to easily link your identity. This should be a normal part of your account creation (this can tie in nicely with another change: getting rid of passwords and using a browser UI for identifying yourself a la Persona, but PGP based). Basically when signing up for Twitter, it should optionally let you upload one of your public keys (via a nice browser UI no less). Twitter (Facebook, GMail, etc.) would then expose a nice API for querying by public key fingerprint: "Who has 0xDEADBEEF?" => "@DeadBeef". Revocation, key updates, all that should be automatic: you revoke your public key and issue a replacement, all your services update automatically.
This is the point where lots of people will raise concerns about privacy: "This means Twitter now must have access to my GMail account! WTF?!". No. This process must be voluntary and optional. If you want to have 200 different identities online, go for it. I don't care to know your real name, I just care to know that I am talking only to the person I intend to talk to. Think emailing a well known developer on GitHub, having never met them. You don't need their real name, you are only interested in them in so far as they publish OSS on GitHub. This allows you to prove that github.com/example is @example on Twitter, example@example.com, example@gmail.com, and HN user "example".
And the benefit to "regular Joe" is that when he emails his accountant, he can now send his credit card number and SSN without fear of eavesdropping.
The only way I can see end-to-end crypto really being adopted is if it's turned on by default everywhere. The selling point can't be the security, because people don't care about security -- the selling point has to be something else. Anything that requires a manual adoption step is going to automatically limit itself to a very niche audience.