After moving from Exchange 2003 to Exchange 2010, I found all my Outlook 2007 users on the LAN were getting this error:
The certificate it was referencing was the FQDN for the external name of the server. But it was accessing Exchange through the internal name. The solution was KB94072
Easy fix once you know what to look for. You're telling Outlook to use the external name - which is resolvable through internal DNS.