You've got more patience than me! If my PC takes more than a couple of minutes to boot, it gets wiped and restored to a cloned fresh install of XP SP3.
I wouldn't be too quick to jump on the hardware bandwagon; it's much more likely to be windows shooting itself in the foot again. If by 'restored' you're referring to system restore then I'm not surprised that it failed to fix the problem. (If 'restore' refers to using the product recovery disk(s) then hardware is a likely culprit.)
For the best chance of fixing your exisiting installation, I would suggest trying a "repair install" of the operating system; if you don't have an XP disk, then you'll need to get hold of one. Failing that it's product recovery disk or fresh install time.
In any case I'd recommend that you backup your data before continuing.