Connection not configured for this service Error for certain users when starting a Flow from PowerApps

[stingray]

Ok this has been driving me mad for days.

I have a number of users that when they click the button in a couple of Apps to submit a SharePoint form and on the success event start a Flow (usually an Approval Flow), nothing happens No Error is shown to them apart from my own custom Error handling which is basically a check to see if anything was returned to PowerApps by the Flow, I cant seem to return any other Error with the built in Error functions from non starting Flows.

To test further, I gave one of affected the users, Co Owner permissions in on the app and tried it in the Editor, after the SharePoint form submitted I did indeed get a red X on the "on success" event which says "Connection Not configured for this service" (see pic) and the Flow says not connected. The App was previously working for this user btw.

I then tried removing the flow in the app as that user abut get an error when re-adding it even though they have the appropriate permissions on the flow.

I also experienced this on a recently created Test account but (Account has E3 and trial licences for PowerApps and Flow), I thought id fixed the issue by removing the PowerApps Trigger in the Flow and re adding it, then removing the flow from the App and re-adding that. My test account was able to start the Flow after this but when trying with the effected user I'm still getting the same error.

Ive also tried Exporting the solution to a different Environment but when opening the App I get an Error for the SMTP connector the flow uses when signing in. The error says "This app needs access to this connection." there's nothing I can do to share this connector and feel its linked to the other issue, in fact I think the issue has something to do with implicitly shared connectors. 

The Flow is to big to just try and recreate as a work around (Even tried copying and pasting in a new flow but it just got schema errors a couldn't fix) , especially before exploring all paths, and really need this issue fixing. I might try and remove the SMTP connectors out the Flow and see if that is the issue but if anyone has any suggestions before hacking my Flow to bits, ive already tried the "Save As" workaround but I cant see that copied Flow in the App to re add and a cant see the newly created Flow to add to the solution.

Don't like having to ask for help but feel like I'm being blocked at every angle trying to resolve this!

Thanks guys and girls!

[Django]

Same here for Canvas App connected to Power Automate Flow in a Power Platform solution in the Default Environment. 

Same solution in another tenant, Default Environment --> no issues

Same solution in same tenant, another Environment --> no issues

Seems like Microsoft is rolling out changes to Production Tenants without proper testing --> See Run Flow - Connection not configured for this serv... - Power Platform Community (microsoft.com)