@Josh Dewling Apologies for the delayed response on this post. Wanted to check does the issue still persists ?
Above configuration in the screenshot looks fine to me, however wanted you to check Prerequisites section where admins need to enable users for the Authenticator app using one of these policies as defined ?
Also do check the sign in logs as troubleshooting step, if these steps doesnt help, let me know we can connect offline to discuss further on the same.
Please send me an email to 'AzCommunity@microsoft.com' with Sub - Attn: Givary and following details in the email body:
Link to this thread/post
We can connect offline and discuss further on this.