
I don't know what Samsung phone you have, but can I check if the advice on "Uninstall for all users" in http://android.stackexchange.com/questions/92025/how-to-completely-uninstall-an-app-on-android-lollipop/92130 (First answer) applies to you? Note sometimes when this happens the list of apps is not alphabetical so check the whole list.
If not, what is the exact error you get?