I've run into this problem before. I fixed it by turning off system restore, running a chkdsk on the effected disks, then turning system restore back on.
Use chkdsk <drive letter:> /f from an administrative command prompt.
To turn on system protection for a particular disk
Open System by clicking the Start button , right-clicking Computer, and then clicking Properties.
In the left pane, click System protection. ...
Under Protection Settings, click the disk, and then click Configure.
Do one of the following: ...
Click OK, and then click OK again.
Also, as srobin has asked... how much free space do you have on the drive. Windows can't create restore points once you get below a certain threshold of free space.