IMAP4 backend service not authenticating to any mailbox on that server.

Scenario: The IMAP4 Backend Service cannot connect to local mailboxes in Exchange 2013 after confirming there was a certificate on the Exchange 2013 server with the IMAP and POP services assigned. The symptom on the client end is failed authentication prompts when connecting to their mailbox via imap using valid credentials and IMAP being enabled on their mailbox.
The IMAP log displays the following: 
NO AUTHENTICATE failed."";Msg=""AuthFailed:LogonDenied
The application log in the event viewer displays the following:
EventID 1102: The IMAP4 service failed to connect using SSL or TLS encryption. No valid certificate is configured to respond to SSL/TLS connections. Check the configured host name as well as which certificates are installed in the Personal Certificates store of the computer.

1. Remove the certificate and re-add the certificate again on that Exhange 2013 server.
2. In Exchange Management Shell run the following: Enable-ExchangeCertificate -Thumbprint XXXXXXXXXX -Services POP,IMAP
3. Restart the Imap and Pop frontend and backend services.