Vista Restore

I am running Vista Home Premium with all updates, this is a NEW build.
I am also running Norton Internet Security.
When I attempt to Restore the System the message on reboot is that the system restore was not successful and no files have changed, this happens both with Norton enabled and disabled.
It have had some success in running Restore in Safe Mode (again with Norton either disabled or enabled) but more often than not I cannot open the BackUp and Restore service. I have run rstrui.exe and the message is that the wizard is running.
Can anyone help with a solution please.