I've the same issue. worked fine for months and months until couple weeks ago, inside sandboxed profile, don't think I changed anything myself, but auto updates and auto remove permissions seem to be enabled by default. Can install updates fine, cannot install new apps. No popup for install, only 'Installing...' followed long after by popup 'can't install {app} see common ways to resolve this blah blah' however there is a gmscompat notification (not popup) upon installing the app 'Action required in play store' clicking on it just pulls up google play store.