After some virus had infected my Windows 7, I did a complete format and re-installed the OS. I was just installing applications and copying back some data when I noticed some shortcuts changing their icons to something I couldnt recognize (Yellow icons in the image below).

Also, a few exe files which previously did not ask for User permission, are now asking for it. Wondering if this is an icon cache problem, I cleared the cache by deleting the IconCache.db in AppData/Local but the problem still persists.
Although I did a full system scan with MS Security Essentials, I'm not sure if this is another virus or some other problem. I would appreciate any suggestions you might have.

Edit: Now even Firefox needs permissions to launch. It's icon hasnt changed, but it's got the 'shield' overlay on it like the other yellow icons.