If anyone had a problem with info 'app not installed for this user' - the comment above solves all issues. First enable the package, then uninstall it.
I've run into this situation by enabling Storage scopes for an app, removing the app and ignoring a prompt to remove for other users. It took me a while to find this thread, so maybe a comment with the exact quote of the message will help someone.