This has just started happening today. One flow on one App, that runs when I open it on my PC, but does not run at all from the device. I can tell from the Flow runs history that it is not executing from any device but mine. Other apps, using the same everything Database, Gateway, Connector, Stored Procedure are continuing to work. This has occurred only since making an unrelated change today.
It seems to be something to do with the latest version of PowerApps studio. I restored the previous Authoring Version, added the Flow back in. Now that Flow runs. Only problem is - I now have to do this with all the other flows. None of the other flows run. Have rolled back to authoring version 31025.25.