System Restore is a popular target for malicious software. The malicious code will sometime make things that could be used to remove it unusable - like System Restore.
First, you should do some scanning with at least these free tools:
Download, install, update and do a full scan with these three free malware detection programs:
Malwarebytes (MBAM): http://malwarebytes.org/
SUPERAntiSpyware: (SAS): http://www.superantispyware.com/
Try your System Restore after this and if you still have a problem, we can proceed.