There is quite possibly a Explorer Shell Hook residing in the following folder:

C:\Windows\System32\win32GI\svchost.exe
If that is indeed the case, that will have to be killed and removed first.

See, if the win32GI folder can be deleted at all. Try CleanupXP+ in Safe Mode with Command Prompt, it should do the trick.

Edit by Judy;
~TL forgot his link to CleanupXP+
Scroll down to post #4 on the link above to download and read instructions on how to use this program.