Strange...
I also noticed IE was very slow to scroll certain pages and there was a huge delay typing text into and forms. I was able to solve this problem by running HiJackThis, and removing a User StyleSheet "C:\WINNT\Web\oslogo.bmp" which as a file didn't even exist at that given location. That fixed the problem with IE, but at the same time fixed the Add/Remove Programs error I was getting.
Talk about obscure... I would have never figured that out focusing soley on Add/Remove Programs issues I've seen on the web.