First, this depends on the specific error they are receiving.
I found a similar issue on the ExchangeServer forums regarding the certification error:
The security certificate was issued by a company you have not chosen to trust
Hope there is something in there that'll help you out.
The first tip regards what he calls 'internal users': When internal user try to use outlook to connect exchange Server, outlook will try to find the e-mail address and exchange server name from AD. After that it will look for SCP and then find the correct the autodiscover server to connect, retrieve settings.
So during the process of connecting to exchange server, it will have to use autodiscover to connect and retrieve user settings. So certificate regard to autodiscover will cause the issue.
Another user states that the certificate warning is considered by "design", i.e. domain joined Outlook 2007 clients would ignore the validity check. This is not the case with Exchange 2010, Outlook 2010. The only way around this is to either purchase a 3rd party SAN certificate from a public CA or if it's for testing purposes only, install Windows 2008 Active Directory CA and initiate a SAN certificate request from Exchange 2010 which your Windows 2008 CA will issue. This works a charm and I have done it a number of times in a dev environment.
Finally, someone provided this tip:
If, as recommended , you want to use an external 3rd party certificate for your exchange server you have to change the autodiscover internal URI for stopping outlook to prompt for certificate warning I've generate a single name ( not SAN ) certificate for our server ie owa.company.com ( the internal domain being company.local ) Then I installed it on the CAS server I used the following command on the CAS server to change the URI Set-ClientAccessServer -Identity "<ExchangeClient Access Server name>" -AutoDiscoverServiceInternalUri "https://owa.company.com/autodiscover/autodiscover.xml" Hope this help stefano