Just an update on my original question (not being able to remove the patch). I finally think I know what is going on.

I had several "Device Menu" patches installed (Brightness, GPS, Data). Once I uninstalled all my "Device Menu" patches, I was able to uninstall this one.

So it appears that some of the patches touch the same code as other patches. It makes me happy that they don't undo each other's work when uninstalling, but I wish there was a better error message (something like "conflicts with other patch") instead of just failing.