I recently went through the same thing. A Repair Install should fix it. Sometimes the Windows Installer file gets corrupted, and then you can't install or uninstall any programs that use it. Some folks around here think it happens when files are patched/modified to install custom themes, icons, start orbs, etc... and I think they are right.
Did you use any other Uxtheme patcher in the past? The one you are trying to install above shouldn't cause the problem, it is a work-around, not a patch.