Outlook 2007 S/MIME Issue

So I recently installed my Office 2007 upgrade over Office 2003. Using
Outlook 2007, I am not able to send encrypted email to myself. I am
just doing this to make sure I can still send encrypted mail. I have
a valid certificate installed, and I can send digitally signed mail to
myself with no problem. When I attempt to send encrypted email to
myself, I receive the following error:

Microsoft Outlook had problems encrypting this message because the
following recipients had missing or invalid certificates, or
conflicting or unsupported encryption capabilities:

It then shows the email address my certificate is for.

This message is odd, because when I go to Control Panel and bring up
the Internet Options applet, click the Content tab followed by
clicking the Certificates button, my certificate shows under the
personal tab as not expired and valid. This is the same certificate I
am using in Outlook. When I send email to myself that is digitally
signed, the received message comes through as signed with a valid
certificate.

There appears to be an encryption problem with Outlook 2007.