Microsoft Authenticator Error - Device does not trust the certificate

When users attempt to setup MFA using the Microsoft Authenticator app they receive an error that states 'Device does not trust the certificate configured on the server. Contact your local IT administrator to resolve the problem.'

Has anyone seen this before? We have tried forcing re-register of multifactor authentication