I have the same problem with exact same error message!
Things that i tried, which didnt help
1. Readding Flow to PowerApp thru "datasource" section
2. Creating a copy of Flow and adding it to PowerApp
3. Redo the connections in Flow and PowerApp
The app is using some flows that are using Sharepoint Online also, they work fine.
But I created a 2 new flows last week and they are cannot be launch from app, receiving this error message..
Flow is running great when it is ran from Automate enviroment using "Test" function.