any anti-virus running?
I seen Norton mess up SR before "disable it if you are running Norton"
Try to run the utility in Safe mode.
Check the System log for any errors that relate to sr or srservice? post them
Do you have space on HDD?
"If you suspect that you do not have as many restore points as you should have, make sure that the data store is the size that you want the data store to be".Right click my computer icon, properties. System Restore Tab, Settings
Srdiag.exe tool uses bin file for all RS files and errors!
Just some quick thoughts to start the trouble shooting process!