I was in the process of porting a production Power App to a dev environment, and I ran into this error.
Unable to add flow
There was a problem adding your service. Please try again later.
The problem was that I tried to add an existing Flow to my Power App, but it was turned off. 
Navigate to make.powerapps.com, locate the Flow you are trying to add to the Power App, turn it on, then try adding to the app.
SharePointed
SharePoint and Power Platform and Stuff
My Flow was on, even though I was a Co-owner, the connection was using a service account when setup. Using the service account, the “Unable to add flow” stopped and it worked.