While deleting the icon cache and rebuilding it may have "appeared" to solve the problem, I believe it will be short lived. I have a funny feeling that the problem will creep back in. Please report back here after a few weeks on whether it really is a long lasting solution.
I have doubts because on my PC when i uninstall Rollback my icons load up correctly suggesting there is nothing wrong with the icon cache? When i reinstall Rollback the problem slowly creeps back in. So it seems that Rollback is incrementally causing the problem to reappear. I suspect that it has something to do with the fact that the more snapshots are taken, deleted etc. the slower my system becomes on boot up. The slow down is not noticeable at first but as time and usage of Rollback continues the slow down is noticeable. Let me say that the slow down in v9.1 is much, much less noticeable that in previous versions (a great improvement). Never the less, its still there. IMO, I think this tiny accumalative slow down somehow interferes with boot time loading of icons.
Just my 2 cents worth.