Not sure if it has been mentioned,
but it sounds to me like a program has set itself up as an icon provider or file type provider, and, well, crashes.
The problem with explorer is that it is too trusting I guess. It's not really it's fault, more the bad software the plugs in to explorer.
I'll use an example to demonstrate how stupid things can be:
My boss recently had a problem after he installed a webcam driver off a intranet. Unfortunately, the driver installer was all fancy, and uses flash. So it had annoying animations and sound effects. Of course, this meant it required flash to run, so there was a separate program to run flash files in the same directory. Instead of using this application directly, the driver installer would setup a file association in explorer. The file association would only work with one file, the driver.
Ridiculous, but it's what it did. However, the problems began later. Because it was badly associated, any file based operation would cause explorer to poll the program checking to see if a file should use that plugin. *any file*. This also had a problem when disconnecting from the intranet. The associated file can't be found, and takes ~30 seconds to timeout.
The end result is that on his machine, everything from right clicking, opening a text file, save dialog, etc, all took at least 30 seconds to appear.
Get a filesystem logger from sysinternals, have a look at what explorer does when opening a file. 90% of it is various programs that have setup general associations that are pointless.