Windows Live Mail Send Encrypted Email I get an Error: Missing Digital ids

I'm trying to send encrypted emails to a contact of mine. They have sent me a signed email with their cert. It's a self-signed cert. I've trusted it. I can see the cert listed under ID's when I look at the contacts edit screen in Windows Live Mail. However, when I try to send an encrypted email to that contact I get an error message:

Windows was unable to locate the digital IDs of the following recipients: [contact email] digital ID is missing

What am I missing?

Thanks.