I have an on going problem with explorer freezing and I have to use task manager to kill the process, obviously this kills all the system tray icons too. In XP's task manager I can go to the Applications tab (different in Vista) and click the new task button. I enter explorer.exe, that starts explorer again and I get the taskbar and the icons back.
So you could try that and see if it works (as when this happens to me my mouse clicks don't work), you may need to use Ctrl+Alt+Del to bring up the Task Manager.