outlook 2007 security certificate has expired error.

I have a windows server 2003 server
Exchange 2007
CA certificate renewed

Our ssl security certificate recently expired and we renewed it with a third party company. We created the csr and uploaded it to the third party which generated the certificate which we downloaded.

We imported the certificate through the exchange ps management tool and enabled it as well. both expired and new cert showed when we ran get-exchangecertificate list command. we ran remove-exchange certificate command for the expired thumbprint and now only the new cert shows when we run the get-exchangecertificate command.

When we open outlook (2010/2007) we still get the box that say "the security certificate has expired or is not yet valid."
The security certificate from passes, so does the certificate has valid name passes.

Could it be the clients are pointing to the wrong place for their certificates? If so how do I find out where they should point to for the certificate that I enabled in exchange?

Any help would be great I am lost and can't figure it out.

Thanks