After making registry changes I always reboot. I don't know if it will make a difference in this case but it sure won't hurt to try it.
NO, you should not have to redo the changes to the registry. Simply reboot and retry.
I haven't experienced this issue personally, I simply searched for that error message, so if that doesn't work hopefully someone else will have some ideas.
I suspect the most common recommendation you will get here is not to use windows back-up at all, instead try Macrium Reflect. Find a link
HERE on our recommended freeware page.