Summary:

You get a message that the Transport Service is unable to offer STARTTLS SMTP verb for "fqdn.yourdomain.com".  So tell it to use the certificate for SMTP as well.

Problem Description:

Event Type: Error
Event Source: MSExchangeTransport
Event Category: TransportService
Event ID: 12014
Description:
Microsoft Exchange couldn't find a certificate that contains the domain name FQDN.domain.com in the personal store on the local computer. Therefore, it is unable to offer the STARTTLS SMTP verb for any connector with a FQDN parameter of FQDN.domain.com. Verify the connector configuration and the installed certificates to make sure that there is a certificate with a domain name for every connector FQDN.

Solution:

Fire up the Exchange shell. =)

1. Identify the certificate currently installed, selecting for information we care about:
   Get-ExchangeCertificate | fl CertificateDomains, Services, thumbprint, status, isSelfSigned
   (we are looking for the FQDN certificate, that is valid, active, and presumably not self-signed.  We want the thumbprint of said certificate.  You can also use a filter of * to get all properties/attributes.  ie. Get-ExchangeCertificate | fl *)
2. Now find the thumbprint of the certificate in question and enable it for SMTP.
   Enable-ExchangeCertificate -services IIS, UM, SMTP, IMAP, POP -thumbprint XXXXXXXX

Further reading:

http://msexchangeteam.com/archive/2007/07/02/445698.aspx