Problems with SSL certificates.

A site has just renewed their SSL certifictaes.
The users of this site now cannot access the site and get the following error message:
“The information you exchange with this site cannot be viewed or changed by others. However, there is a problem with the site’s security certificate…..”
If a person goes into the site, who has never been there before everything works fine.
I have cleared out all of the certificates from their IE as well as cleared the SSL cache to no avail.

Where to now?