I recently applied a re-issued certificate from GoDaddy to a customers Lync Edge servers. The certificate was was issued by the Starfield Secure Certificate Authority – G2 certificate authority (CA), which was different to the previously issued certificate. After applying the certificate we noticed that voice mail transfer to Office 365 Exchange Online UM stopped working. The Lync Edge server event log was reporting lots of certificate errors to exap.um.outlook.com. After logging a ticket with Microsoft they confirmed my suspicion that the CA was not trusted by their service. GoDaddy were nice enough to re-issue the certificate using the old/previous CA, and after applying it to the Edge server the problems went away 🙂
EDIT: Make sure that you have correctly installed the root and intermediary certificates. You can test your installation here – https://www.sslshopper.com/ssl-checker.html
For anyone googling the issue you can resolve the issue yourself by re-keying the certificate using the Godaddy control panel and select "SHA-1" instead of "SHA-2" for the encryption cypher. This works for both the Starfield and the GoDaddy roots
Hope this helps.