Hi,
Please confirm whether the issue happens to all users or specific users to narrow the issue to client side or server side.
If the issue occurs on all users, we could run the following command to check the autodiscover service.
Get-ClientAccessServer | FL Identity,AutodiscoverServiceInternalUri
In Exchange server, please run the following command to check your new certificate settings:
Get-ExchangeCertificate | fl
Meanwhile, I suggest you can do an Outlook connectivity test with https://testconnectivity.microsoft.com/ and see what went wrong.
If the issue occurs on a specific user, I suggest you can create a new profile to test.
Best Regards,
David