I’ve seen this several times. Usually, it’s due to having a signed release version on my phone, then trying to deploy the debug version on top. It gets stuck in an invalid state where it’s not fully uninstalled.
The solution that works for me is to open a command prompt and type:
adb uninstall my.package.id
That usually completes the uninstall in order for me to continue development.