I too am having this issue. It seems to be trickling into other areas of my
computer (for example, it gets very confused about some of my shortcuts,
particularly one in my Startup menu, which is now pointing to a non-existant
location).
I believe it to be the result of a recent Windows Update; unfortunately
removing the update didn't seem to fix the problem. I think it was either
Vista update KB931836 or Udate for .NET Framework KB932471. There was also
an update for Media Center for Windows Vista KB935652 that happened right
around the same time.
Like other users in this thread, my ability to uninstall programs is gone.
Some of my currently installed, properly working software does not appear on
the list of programs at all. The entire "Publisher" column is empty.
I also found that at the same time, the Roxio (or HP) Digital Media Archive
started repeatedly asking me for updates and files that it couldn't find. Of
course, I couldn't uninstall Digital Media Archive, so I had to use "Windows
Install Cleanup" from the Windows troubleshooting website to uninstall it and
then re-install it from the web.
As Rich D noted below, anything installed SINCE the problem started appears
to be available for uninstalling as normal.
Eric Noah