You say you have backed up to an external drive, so I assume you must have attached one at some stage. I too had problems restoring 'til I switched off windows system restore from monitoring my external drive. It seems to me windows restore gets in a hissy if there's a drive there one time, and not another (i.e turned off or detached) as it's not sure it knows all the changes that have taken place on the SYSTEM - i.e not just your PC's internal HD.
Look in system restore with you external drive attached and on and see if it's monitoring it, then tell it to stop! Then set a new restore point and test it. Worked for me..., but of course doesn't help with your old restore points I'm afraid