When you say it doesn't work, does an error appear, does it show up blank, or does it not open at all? Are you also saying that the Add/Remove programs icon doesn't even show up in safe mode? (that would be bizarre).
My Dial-a-fix program can fix a lot of the scripting-related errors with most Control Panel applets. Give it a shot, it's non-destructive: http://wiki.DjLizard.net/Dial-a-fix
I'd suggest downloading the Light version and checkmarking everything in box #5 and then hit GO.