I think it's because there still isn't a good metaphor that covers up the complexity of public key encryption. Such a metaphor is a prerequisite for a UI that the average user can comprehend.
First, I think we should rename the keys to 'locking key' and 'unlocking key'. I've had people still scratch their heads at 'public/private' a few days after I've completely explained the concept to them. They find it easier to understand that a lock-only key can be shared freely while an unlocking key has to be guarded.
Second, key exchange and storage has to be transparent to the user. The process can go something like:
1. User 1 clicks 'setup secure email with user2@domain.com'
2. User 2 receives 'user1@domain.com wants to setup secure email with you. y/n? (first make sure that this is really his/her email address)'
3. Based on the response, keys are automatically exchanged and stored.
4. Provide a 'compose secure email' option
5. When adding email recipients, the encryption happens automatically. Recipients with no keys are not allowed in secure mail, obviously.
6. The encrypted form is never displayed on screen. Only a lock icon.
7. On the receive end, a passphrase prompt is displayed when a secure mail is opened
Perhaps commercial/proprietary clients already do this, but none of the free ones I've tried are like this. So I'm stuck with using GPG with only with those who understand how the thing really works.