If that's the case then there are problems.
In normal mode, (not safe mode), when you open the Task Manager by CTRL+ALT+Del, can you goto File > New task (Run...)? If so, can you type in explorer.exe and click OK or press the Enter key on the keyboard?
If you can do all that, hopefully explorer will start and display your Taskbar and desktop icons.
I have a Windows XP SP2 laptop that hadn't had it's virus definitions updated in a while (because it was a scheduled thing and I never had it turned on at the right time! duh).
So, I updated the definitions, then ran a full scan (Trend Micro-2008). It found 31 issues and two Trojans. It deleted the cookies, quarantined the Trojans and I re-booted as instructed.
Now it boots fine, but doesn't show the desktop, no icons, no status bar, nada. It just shows my background wallpaper image and sits idle. It responds to mouse movements, and ctl-alt-del (shows no apps running - none using CPU), but does not respond to mouse clicks, the Alt button, F keys, etc.
I re-booted to safe-mode and it hangs without showing the desktop, re-booted to last known good config. - no difference, re-booted to debugging mode and no messages, no difference.