Your first port of call for System Restore problems should be the System Restore Troubleshooter, which you'll find here http://support.microsoft.com/?kbid=302796. However, it's also possible that one of your Restore points has become corrupt, in which case you'll need to disable System Restore. This will delete all existing Restore points and then re-enable it. To do so, right-click My Computer on the Start menu or desktop and choose Properties -> System Restore tab. Tick the 'Turn off System Restore on all drives’ and click Apply - you'll be told that all existing Restore points will be deleted, so click Yes, at which point the Restore points will be removed. Now remove the tick and click Apply again to re-enable it.

You can now test that System Restore is working properly by creating a new Restore Point and then immediately attempting to restore your computer to that point in time. Hopefully, now you'll be successful.