I have the same problem. We use Outlook.
I found the steps below, but they do not tell you that the ID file must be on the workstation with Domino Adminstrator loaded on it. I've tried to recertify them on the server, but I recieve errors. When I copy the ID file(s) to my C drive (in my Lotus\Notes\Data folder with the cert id and my Admin id), it works.
From Domino 5 Administrator Help
Recertifying a Certifier or a User ID
1. From the Domino Administrator, click Configuration.
2. From the tools pane, click Certification - Certify.
3. Choose the certifier ID used to issue the certificate, and click Open.
4. Enter the password for that certifier ID, and click OK.
5. Choose the certifier ID for one of the following:
Organizational unit
Server
User
Organization certifier (when the Organization certifier is used to certify itself)
6. Enter the certifier ID password and click OK.