If you have root on your phone you can try checking if there are any files left in the app directory after you've uninstalled the app and removing them manually.
This is strange though, I'd expect uninstall to work or if not then wipe data + uninstall.
