Hi,
Ran into the same issue setting up a demo for a client.
I solved this by synchronising the Android Enterprise Apps, then I could install it on the phones.
When I tried to aprove the apps when I installed them, I got a error saying that Aproval failed.
It seems that it's the Aproval for the app is missing.
You can see the last sync status under System Manager / Overview, and sync from here.
If you go under Systems Manager / Apps, and add the column "Android Enterprise Aproved" then you can see your aproval state.
My Apps was not aproved, you can sync from the Overview or from the Apps page under accounts. After a sync, I could aprove the Apps, and they installed on the phones.
Hope this helps