It may not happen a lot but, I just wanna share what I found tonight.
So, basically, what do you do when an icon of a file doesn't appear? The icon that the software attribute to it when associated with it?
Well, some will try tweaking programs to associate it an icon. Some will try uninstalling then re-install the software. Some other will try to make the software re-associate the files again in the registery. I don't say that those won't work. But... imagine... what if those three solution above doesn't work and that there's still a blank icon next to the file?
You may scratch your head a lot right?
If you want to cause the problem do this in order :
1. Install foobar2000 and associate every files it supports with it.
2. Install The KMPlayer 2.9.4 build 1434 (2.9.4.1434) and associate every video formats to it.
3. You'll see that the .mp4 format is associated with foobar2000. It should be The KMPlayer's since it's mainly used for video.
4. Get this little app Brink linked us to...
Unassociate File Extention Type - Vista Forums Use it to unassociate the .mp4 file.
5. Now, re-associate The KMPlayer to MP4 files. It should play them instead of foobar2000 but... where is the icon. Trying the 3 first solution won't work.
So, here's the solution : (using The KMPlayer has an exemple)
1. Start orb -> search regedit -> Open Regedit
2. HKEY_CLASSES_ROOT -> KMPlayer.mp4
3. Open it and you should see a folder called "ShellEx". And, if you look at other folders, that have their icons, that folder isn't there. So, why is this one alone? Well, you figured it out. That folder shouldn't be there.
Delete it.
4. Log out and back in... the icon should be where it is supposed to be now.

If not, just rebuild the Icon Cache.
All because of an "Icon Handler". :\
Oh well, I hope it helped or informed you
Thanks to this post :
MP4 Icon Problem. - Page 2 - The KMPlayer's Forums