Microsoft Who App Permissions Failing This App does not Exist or has been uninstalled

Hi Everyone,

Trying to roll the "Who" app out to my organisation. I'm getting half the users when the select "Allow" to give it permissions getting the below error message:

Who

I'll need your permission to perform searches on your behalf. Go ahead and click Allow

This action can't be performed since the app does not exist or has been uninstalled.

I have had user reinstall Teams. Check the teams admin console and I can't assign global permissions for the app there. This is on the Teams Desktop App, Windows 10 and 11. And not all users.

Anyone have any ideas what might be going wrong or how to fix?