Sounds like you may have a process running which a restart can't handle but a Shutdown kills sucessfully.
Worth taking a peek at the Task Manager before shutdown to see what's going on. Could be a worm or adware stuff running there somewhere. It's amazing how much crap can infilitrate a system if it's been used for downloads.
However, I'm not familiar with XP - Win2000 and Win98SE here.