Maybe this will help?
http://support.microsoft.com/kb/841568When I had XP the system restore and safemode stopped working and I ended up using BartPE to bootup and manually replace the system restore files.
The method is very technical and I don't know how to do it off the top of my head or where to find it on the internet.