System Restore has been known to become non-functional in many cases. It is
usually remedied by simply turning off System Restore and then turning it
back on - with the obvious drawback that you lose all previous restore
points.
I have found it a good idea to occassionally do this when I know my system
is working fine to insure I have a functional System Restore. I also
manually make restore points before most installations.