Exchange 2013 Hybrid Mail 'Pending' - RootCAType Certificate Issues

I manage an Exchange 2013 deployment at work which is configured in Hybrid with Office365. Recently we had to change our SSL certificate that was being used for both TLS for the hybrid connection and also for our client facing DNS names. Due to changes with our 3rd party SSL certificate provider, this was a new SSL certificate installation rather than a renewal. I generated the certificate and installed it onto all of the Exchange servers on-premises and during our change window, made the changes to bind the services to the new certificate and then ran the Hybrid connection wizard to update the certificate used in our On-Prem send connector to Office365 and also to the receive connector in our Office365 tenant.