The Windows icon cache is a fairly buggy creature. You can solve this in one of the following ways:
HKEY_LOCAL_MACHINE\\Software\\Microsoft\\Windows\\CurrentVersion\\Explorer and add a new String Value called Max Cached Icons. The default value is 500 - try increasing it to 2048 (see Q132668 in the Microsoft knowledge base for more details). TortoiseProc.exe /command:rebuildiconcache