Wild guess is that you are talking about a non clean restore, ie take my mess of a hard drive and try to put XP back into a new state, but leave all my junk alone so I don't have to reinstall my games etc. My guess is that when your drive is REALLY hosed the limited smarts on the restore CD can't put stuff back without messing up some of the stuff you want to keep. Time to choose, live with the troubles, or do a clean install.
OTOH maybe you have some pesky hardware problem or a virus.