I had this same problem after my hard drive failed (C: Windows XP). I installed a new drive and restored the drive from a backup of my C partition and everything worked - except system restore. I tried stopping and starting the System Restore service, but that did not help. I discovered the following steps will cure the problem, though you will lose your existing restore points, which is not a horrible thing when you have a backup.
(1) Click on the Start Menu,
(2) Locate "My Computer" and right click, select Manage. If "My Computer" is not showing on your start menu, you can also find it in Windows Explorer.
(3) When the computer management window appears, click the + to Expand Services and Applications and then click on Services. You will see a list of all your services.
(4) Find the System Restore Service in the list, right click on it and select Properties.
(5) On the General tab, change the startup type to "Disabled" and then press OK.
(6) REBOOT THE COMPUTER (this step was essential to get this to work)
(7) Repeat these steps 1-5, only set the startup type to "Automatic" in step 5. There is no need to reboot again. Your problem should be fixed.
If you have large disk drives, you may want to modify how much space System Restore uses on each drive. I installed a 1 Terabyte drive and it wanted to use a ridiculous 12% (over 100G). I set that down to 1% and have not had any problems.