When uninstalling an app using the usual pre-Lollipop approach (e.g. dragging to the "trash bin" icon, or from App info > Uninstall), it's only uninstalled on the current user. This can be confirmed by the app showing "Not installed" on the stock app manager. Android will detect that the app is still there, preventing the user to install the app with the same package name.
The root cause is Guest account (if it's activated), that when an app is installed, it's automatically installed on all users. So, it is also required to uninstall the app from there, which can be troublesome in daily usage.
There are some approaches to uninstall the app completely (ordered by practicality):
- (from the owner account) Go to Settings > Apps, find and open the app info. Then, open the overflow menu (3 vertical dots), and choose Uninstall for all users.
- (from the guest account) Deactivate the guest account if it is not needed (for more info: Removing the default guest user account from Android Lollipop)
- (from PC) Enter
adb uninstall <package> on the command prompt/shell. This is the same as "uninstall for all users"
- (from guest/other accounts) Find the app and uninstall it normally.
- In case it can't be uninstalled, try removing the account and creating a new one, then try finding the app and uninstall it again.