Self-signed certificate for email encyption?

I wanted to simply create a self-signed cert for encrypting email using the Keychain Certificate Assistant. I overrode the defaults and selected Digital Signature and Data Encipherment under Key Usage, and under Ext Key Usage: Email Protection, Apple .Mac email signing, and Apple .mac email encryption, and used my mac.com email address.

This showed up in my Keychain just fine, I selected Always Trust and sent a digitally signed email to a friend. He accepted it and set Always Trust as well. He also created a self-signed cert with the same settings as mine (but with his mac.com email address) and sent a digitally signed email to me.

However, we cannot encrypt to each other after all this. The Lock icon is grayed out and Mail only lets us sign email to each other. We are both on Leopard 10.5.8 with Mail app 3.6.

Anyone know what I might have done wrong? Does one have to get a cert from a Certificate Authority? Can we get one from MobileMe for email encryption (we used to when they first offered the ichat/email cert, but removed the functionality after the first renewal back in 2007)

One last item: we both have MobileMe, so have the certificate that Apple provides for encrypted ichat - can one have 2 certificates for different purposes on the same account?

Thanks.