Ok,
I had the same issue for past few days since after the installation. Everything in my test environment worked but for some reason after deployment in production, every one is getting this message in their communicator but myself.
After much research, nothing. I accidently came upon this. If you are creating a certificate from your company's CA, you must add that certificate on local machines. Try this and this might help...
Go to site http://<CAServer>/certsrv
Select the option to "Retrieve the CA certificate or certificate revocation list", click Next
Download CA Certificate to your computer and save it to your desktop
Click Start -> Run
type in "mmc" and press enter
Click File, Add/Remove Snap in
Click Add, Select Certificates and click Add
Select Computer Account, Local Computer
Click Finish, Close, and Ok.
Expand certificates, Trusted Root Certification Authorities
Right Click Certificates, All Tasks, Import
Click Next, Browse the cert you just saved on your desktop, click Next, Next, Finish
Communicator now should start working without restart or logging off.
Good luck.