On a fresh format/install I would suggest some driver issue. How did you re-install and where did the drivers come from?
Why did you re-install?
Other than that, normally this points to virus damage. Did you connect to the internet before installing any firewall or anti-virus protection?
If so, look up BHO's on Google, (Browser Helper Objects). Whilst they are used as helpers for IE, Windows integrates IE with Windows Explorer and the Taskbar closely, so any problems with BHO's will often affect all 3.
I would remove all BHO's.
As my title suggests I'm having problems with windows explorer which is also linked to the windows taskbar :(. Anyhoo as soon as I start an explorer windows in Windows XP SP2 (should i upgrade to sp3?) my taskbar and all my desktop icons disappear and for some reason I can no longer right click on the desktop. I can still run programs through taskmanager, and I figured out restarting the shell by running the explorer command brings back my taskbar and desktop icons back to normal. Anyway if I try to reopen the explorer window the whole problem starts up again. Did I mention that the explorer window stays up for about 3 seconds before it and the taskbar disappear? By the way yes I've tried system restore; no dice because my computer is freshly formatted and in order for me to back up my stuff and format again I'd have to use windows explorer. Also when I tried booting safe-mode my computer restarts.
Any help at all would be great!
Thanks : )