Exchange 2010 creates a self signed certificate by default, that only contains the short machine name. This can cause certificate issues as the server may be addressed via it's fully qualified domain name, and also as the certificate issuer is not trusted.

List the existing certificate

[PS] C:\Windows\system32>Get-ExchangeCertificate -DomainName "SERVER"

Thumbprint                                Services   Subject
----------                                --------   -------
CF69890AC32D70CA1367CE6EB73DF6A29C9E5EC4  IP.WS.     CN=SERVER

Check the AutoDiscover URL

[PS] C:\>Get-ClientAccessServer |fl identity,autodiscoverserviceinternaluri

Identity                       : SERVER
AutoDiscoverServiceInternalUri : https://server.domain.com/Autodiscover/Autodiscover.xml

Check the Web Services Virtual Directory URL

[PS] C:\> Get-WebServicesVirtualDirectory |fl identity,internalurl,externalurl


Identity    : SERVER\EWS (Default Web Site)
InternalUrl : https://server.domain.com/EWS/Exchange.asmx
ExternalUrl :

Generate a new certificate request

[PS] C:\>New-ExchangeCertificate -GenerateRequest -KeySize 2048 -SubjectName "c=au, s=WA, l=Perth, o=The Ether, ou=IT, cn=server.domain.com" -DomainName server,server.domain.com -PrivateKeyExportable $True -IncludeAutodiscover -IncludeAcceptedDomains

-----BEGIN NEW CERTIFICATE REQUEST-----
MIIE0zCCA7sCAQAwdjEkMCIGA1UEAwwbYWxleDAxLmFuZ2xpY2FuaG9tZXMub3Jn
...
pSl3ZjDSWVA3FHai8PotkbBykaVsbJNIGYyj7NDo6YRKiZkj+bga
-----END NEW CERTIFICATE REQUEST-----

Generate a new certificate
From https://ca/certsrv/
- Click Request a certificate
- Click advanced certificate request
- Click Submit a certificate request by using a base-64-encoded CMC or PKCS #10 file, or submit a renewal request by using a base-64-encoded PKCS #7 file.
- Paste the certificate request text from above into Saved Request
- Select the appropriate template and click Submit
- Click Download certificate
- Save the certificate file e.g. C:\certnew.cer

Import the certificate to generate the certificate with a private key

[PS] C:\>Import-ExchangeCertificate -FileData ([Byte[]]$(Get-Content -Path C:\certnew.cer -Encoding byte -ReadCount 0))

Thumbprint                                Services   Subject
----------                                --------   -------
0FC4A3DAAC2B70C1C23F68C2D22CCFFBC2EB859E  IP....     CN=server.domain.com, OU=IT, O=The Ether, L=Perth...

Assign the new certificate

[PS] C:\>Enable-ExchangeCertificate -thumbprint 0FC4A3DAAC2B70C1C23F68C2D22CCFFBC2EB859E -services "IIS,POP,IMAP,SMTP"

Confirm
Overwrite the existing default SMTP certificate?

Current certificate: 'CF69890AC32D70CA1367CE6EB73DF6A29C9E5EC4' (expires 18/10/2013 1:56:04 PM)
Replace it with certificate: '0FC4A3DAAC2B70C1C23F68C2D22CCFFBC2EB859E' (expires 18/10/2013 2:58:06 PM)
[Y] Yes  [A] Yes to All  [N] No  [L] No to All  [?] Help (default is "Y"): y

Remove the self signed certificate

[PS] C:\>Remove-ExchangeCertificate -Thumbprint CF69890AC32D70CA1367CE6EB73DF6A29C9E5EC4

Confirm
Are you sure you want to perform this action?
Remove certificate with thumbprint CF69890AC32D70CA1367CE6EB73DF6A29C9E5EC4 from the computer's certificate store?
[Y] Yes  [A] Yes to All  [N] No  [L] No to All  [?] Help (default is "Y"): y

The Subject Alternative Names can now be seen in the certificate:

DNS Name=server
DNS Name=server.domain.com
DNS Name=autodiscover.domain.com
DNS Name=domain.com

Configure SSL Certificates to Use Multiple Client Access Server Host Names
http://technet.microsoft.com/en-us/library/aa995942.aspx

Security warning when you start Outlook 2007 and then connect to a mailbox that is hosted on a server that is running Exchange Server 2007 or Exchange Server 2010: "The name of the security certificate is invalid or does not match the name of the site"
http://support.microsoft.com/kb/940726