I faced an another use case where I got the similar error.
When At first I got the error, I panicked, and removed /data/data/{package.name}
After that I tried, and my problem was still present.
Then I tried uninstall, it failed.
I then removed the apk file present in /system/app
(required root access), and tried uninstall and it was successfull.
After that I tried re-installing the apk, it worked.