After updating a certificate on Exchange 2013 I always remove the old certificate. This lead to the complete back-end not working properly anymore. A quick search on Bing concluded that Exchange does not bind the certificate to both the Default Web Site and the Exchange Back End, but purely to the Default Web Site. Manually binding it to the front-end fixed that issue.