Power Automate Add Member to Team Action is failing with "Forbidden" with valid connection credentials

I have a multistep Power Automate, which had been working for month. It does a variety of actions including, creating a user, adding that user to security group and then it adds that user to a team ("Add Member to Team).

In the flow, the step has the following error:

{
  "error": {
    "code": "Forbidden",
    "message": "You do not have permission to perform this operation.",
    "innerError": {
      "message": "You do not have permission to perform this operation.",
      "code": "AccessDenied",
      "innerError": {},
      "date": "2022-09-19T16:55:25",
      "request-id": "SNIP_GUID1",
      "client-request-id": "SNIP_GUID2"
    }
  }
}

On the flow on the right hand side the Error details has the following.

Action 'Check_if_user_exists' failed
Error Details
Resource 'newhuser@mydomain.com' does not exist or one
of its queried reference-property objects are not present.

This has been working for months. Just started failing. The weirdest thing is, the user is added to the team. The step fails though and the rest of the flow does not run.

I've tried resetting the connection by switching the account and selecting my account again. The account has all the right credentials to do these actions.