Just wanted to add my 2 cents here. I had a similar problem with my icons after a windows update. I found out that one of the updates was causing the problem...don't know why. I went through my recent updates and deleted them one by one until I found the one that was causing the problem (if the update wasn't causing the problem, I reinstalled it before deleting the next update just to make sure it wasn't multiple updates causing the problem). This didn't make me real happy but it did solve my problem with icons. I then had to be sure to turn off automatic updates and make sure that any future updates didn't include the one that caused my icons to disappear!
I'm not sure how long I had to do this but eventually the 'bad' update quit showing up in the downloads.
Like I said, just my 2 cents worth. (Course, we all know that 2 cents isn't worth much these days, right?)
Hope you get a solution!