Do you by any chance use Norton AV? If so System Restore will only work if you temporarily disable Norton.
If not, then have you tried running System Restore in safe mode?
Go into Services (Windows key+R and type services.msc) - and scroll down to Volume Shadow Copy - make sure it is started and on Automatic.
Finally - if one of your restore points is corrupted then System Restore won't work. The way to correct this is to turn off system restore then turn it back on again. You will lose all the restore points, but as you have no problem at present it might be worth doing, and then create a new restore point. Once you've built up a couple of restore points it should then work OK.
1. Go to Start
2. Select Control Panel
3. Select System and Maintenance
4. Select System
5. Select the System Protection link
6. Uncheck the disk drive for which you would like to turn system restore off
7. Click the "Turn System Restore Off" button. System Restore will no longer monitor and create restore points for the unchecked disk drive.
8. To turn the system restore feature back on, recheck the drive in step #6 above, then click Apply.