System Restore is, in my experience, a waste of space. Every time I've tried it, it has only partially restored (giving me a sort of hybrid of two restore points) or not worked at all as you described.
If your computer is playing up enough to warrant the use of System Restore, the best thing do to is back up as much data as possible and start again with your hard drive. As an extra tip, if you only have one hard drive, when reformatting it might be worth considering partitioning your hard drive if you haven't already; use the primary partition for programs and OS files, and your other one for important work, documents, personal stuff etc... that way, if your OS corrupts and you need to reinstall, you can get away with having only one hard drive and not losing loads of important stuff.
(If you're already doing this, I don't mean to insult your intelligence by suggesting it - there are people far more qualified to talk about this sort of stuff than me, but it's just a helpful hint to anyone who may not already be doing it!)