this happnes more often than you think as microsoft wrote crap software. Have you tried doing it from the vista cd, if you put it in then go past the first screen, there is an option for repair click on it and try restoring the system from there. If that doesnt work try goin in in safe mode by pressing f8 at start up. If that doesnt work let me know.
When you are informed that your system has failed to restore, does the message also mention that it could be due to anti-virus software, or failure to access a file.
I have had exactly the same problems. I was running Zone Alarm and AVG anti virus. Until I uninstalled both of these programs I could not get my system to restore. Having removed them and switched to Commodo and Avast it works perfectly.