[AdmiralAsshat]

This is an option, and like I said, this will probably happen when I decide to get a new phone, because I imagine the key will change. And for the paranoid, yes, you can do the verification. My point was that initial exchange (which, in my mind, is the most nerve-wracking part of the whole PGP setup when dealing with a layman) is completely automated.

Plus, once I sent her a TextSecure message, I sent her an SMS to confirm that she received the first one. Now granted I guess someone could hijack her SMS too, but you could swap that out for any second-step verification of your choosing: an SMS, an e-mail, confirming in-person that we're receiving what the other person sent, etc.