If the settings is not restting due to a setting on a higher level of the folder hierachy tree, then it is likely that you may have a virus, but I have not heard of one doing things like this.
This sort of behaviour is more likely some setting overiding your customisation.
When making the changes are you in administrator mode or user mode, as they can often make a difference as to the setting being saved as a permanent change and not just a session change.
Now this next bit is very tricky so be careful.
When you go 'Start' >> 'Run' and type 'Regedit' you open a program called the Registry Editor errors in this can cause problems but if you are careful you can fix many things. The changes are saved as soon as you close the program so you need to write down settings before you make changes incase you need to return them to the previous setting. Once you find a setting you can change it by selecting the setting in the right hand window and right clicking to bring up a menu box and select modify, this then opens an action box. Most settings are changed in the bottom entry box.
Some of the Registry settings for the folders are at
HKEY_CLASSESS_ROOT - Folder - Defaulticon
my setting is %SystemRoot%\System32\shell32.dll,3
HKEY_LOCAL_MACHINE - Software - Classes - Folder - Defaulticon
my setting is %SystemRoot%\System32\shell32.dll,3
check if your settings are the same, if not change them and then see what happens over the next few days.
But be careful when working in the Registry.