Ironically, a lot of viruses now use Windows' own security policies against itself. I bet the answer lies here:
Start > Run > gpedit.msc
Expand 'User Configuration' > 'Administrative Templates' > 'Control Panel' > "Add or Remove Programs".
You'll see possible restrictions and other behaviors in the right pane, some of which may keep you from opening Add/Remove Programs. Check them out by double clicking on them and check to make sure their values make sense.
It could very well be something else too, and it wouldn't surprise me if you have other issues with system utilities like msconfig, system restore and such.