Yes - I had this problem yesterday! Some malware.. But there have been soo many more issues since... I can't remember exactly which thing caused or solved it... It was REALLY annoying! Is the problem maybe explore.exe (vs explorer.exe)?
I'm so sorry I can't remember exactly - but I can tell you to try a few things. First do Windows Update and make sure you've got all of your critical updates...(for some reason that rings a bell).
This is what I generally do - after cleaning up temp files, cookies, etc., I run I run Spybot, AdAware, CWShredder and TrojanRemover. After that clears away stuff - check add/remove programs for crap - Kazaa, etc. Remove from add/remove if you can. Then look in program files for crap to see what you've got. Then you can proceed to HijackThis. If you don't know how to read the HijackThis log, you should post it!
Let me know how you fare!