Heya,
I had the same issue on Friday and even left a comment about it in this thread. There seems to be a bug in the OOTB functionality when you try to change what group you want to share with. It's like it's cached in dynamics...
However today I found a work around.
1. If you have the admin permissions, go into the Power Platform Admin Centre (Dynamics 365 Apps)
2. Find the Teams environment of the power app you are trying to update.
3. In the "Resources" area click on the Power Apps link
4. Here you'll find your Power App. Click on the "..." and select Share
5. Remove the irrelevant group, if it's still displaying.
6. Add the new group and you're good to go.
Hope that helps!