Sorry to hear that your users are facing authentication issue. We have seen issues where if user had accidentally logged in with a personal account, they are no longer able to login again. We have also seen issues related to the Microsoft Authenticator app not responding properly, causing authentication failure. Some of these failures have also happened due to system restrictions for Android devices (See here.)
In most cases, uninstalling and reinstalling both 'Power Apps' and 'Microsoft Authenticator' app will resolve the issue.
Please have your user follow the steps below and let us know if it helps:
Back up your 'Microsoft Authenticator' accounts
Uninstall 'Microsoft Authenticator'
Uninstall 'Power Apps'
Reboot the device
Reinstall 'Power Apps'
Reinstall 'Microsoft Authenticator', add back your accounts