I had the same problem:
* first installation of a patch did correctly
* second one did not
So i uninstalled the patch component (com_patch), the installed the 2nd component with success
AND....
the first one were not unistalled !!!
That's why you get the message
"
You are SAFE to Uninstall this Patch Component
"