If you believe the problem to be profile related, you could always try removing the Users profile.
Rename the profile directory (DO NOT DELETE), this will force the system to reload the profile.
Another possibility that i have seen before is that spyware had modified the HKLM\Software\Microsoft\Windows NT\CurrentVersion\Winlogon\shell key.
This should be set as explorer.exe, malware can change this key to point to there own exe's that load malware then loads your explorer process. If the exe that this points to has been removed by the mal ware remover application then it can cause the problems you are experiancing.
Check the key is pointing to explorer.exe, if it is check the presence of explorer.exe on the loacal system. If its not there extract it from the setup CD. There will be a KB article on how to do this.