I think I have found the root cause of this issue, and it seems to be a rather serious bug.
During my trial subscription, I added the new 'Map' input and 'Address Search' to my app to play around with them. There was still some functionality issues, so I removed them from my app. Well, when you add these inputs to an app, PowerApps automatically creates and add a connection for "Spatial Services". In the list of connection, it is not shown as a Premium connector. However, in an attempt to troubleshoot this, I "Saved As" the problem app, and when starting the new copy the first time, I had to sign in to the existing connections.
Aha! In the list of existing connections, was "Spatial Services", designated as a Premium connection. Now I am trying to disconnect the Spatial Services connection from the app to see if this downgrades the app license designation.
Nevertheless, this is certainly a bug that needs to be ironed out with these new inputs.
