There are two additional things to check. Caveat: I'm on windows 7 so the advice may not apply.
Easiest is to go into the personalize screen and uncheck the part where it allows a theme to change icons (especially if you recently installed or changed themes).
Next would be to make a registry change - here's one thread that discusses the process. You have to find the parts by a user whose name is something like security14 (sorry I forget, too lazy to go back, just scroll down & you'll find it).
If your using XP this usually happens when an application such as a game or other program changes the screen resolution when its operating, not much you can do about it if this is the case...its just what Windows will do to maintain the icons on the desktop at lower resolutions.
If its Vista or W7 your theme may be corrupt, you can do a search on google for the specific issue if its theme related...there are different repair procedures for different problems.