If you werent given a OS disc when you bought the PC and you are legally running your own licenced copy of XP it may be on a seperate partition on your hard drive. Some PC suppliers do this. (Dell)
You have to access this using keystrokes at start up to restore to the as shipped condition.
Details are in the manual.
Daft as it seems the manual is often on the Hard Drive. If it is transfer to a USB Key.
ive seen a similar problem with a friends computer and it was Norton security that actually deleted a .dll file from system restore.
Do a google search on the actual error message you are getting, the solution is probably posted several times over on the net.
the problem with windows system restore is that its just plain crap. its a bit late now but when you get your system going again you should think about using a 3rd party imaging program or something.