Действительно,
Rebuild Icon Cache помогло восстановить внешний вид ярлыков.
Восстановление значков (ярлыков):
Сделать это можно через
командную строку вводя такие команды:
ie4uinit.exe -ClearIconCache
taskkill /IM explorer.exe /F
DEL "%localappdata%\IconCache.db" /A
shutdown /r /f /t 00
либо
вариант по проще - скачайте и запустите
Rebuild_Icon_Cache.bat который удалит Icon.db и восстановит кэш значков: