Greetings,
this morning one of the users in my domain started having a problem authenticating into a PowerApp I created for internal budget tracking. The app uses two SharePoint (Online version, nothing is on-premises) tables to store the relevant data and a Flow for triggering and doing the necessary Patch table functions.
I just launched the app, a few other users already successfully used the app and everything that goes with it. Only one has an issue which looks like the below picture:

After clicking on 'Fix connection', a little loading bar appears for a few seconds, then disappears and we're back to the same message as above.
What we've tried:
- Clearing cache & cookies
- Incognito window
- Different browsers (Edge, Firefox, Chrome)
- Completely different device
- Changing user permissions to 'Edit' on the SP Page (other users can't access the SP site itself at all, only the table within)
Nothing seems to work, the user is always stuck on the same error. The user is in the proper Security Group which has access to the table (not that it matters, since I've tried solution #4).
I've checked his sign-in logs and they show an "PowerApps - apps.powerapps.com" successful sign in, but the user still can't enter the app itself.
Seems to me like an authentication issue, or maybe more specifically an issue with forwarding the successful auth to the proper PowerApps server, since the auth attempt itself is successful. Only problem is the user is still not let into the PowerApp itself.
Anyone has any ideas or has been having similar issues? Thanks.