In Android 5, check your settings -> apps. Instead of deleting for just the active user (since android 5 can have multiple users and my phone had a guest user) tap on the accessory button in the top right corner of the action/toolbar and choose "uninstall for all users". It appears that in Android 5 when you just uninstall from launcher you only uninstall the app for the active user.
The app is still on the device.. This had me dazzled to since I was trying to install a release version, didn't work so I thought ow right must be because I still have the debug version installed, uninstalled the app. But than still couldn't install.. First clue was a record in the app list of the uninstalled app with the message next to it that it was uninstalled (image).