I've had this error after trying to let users in my domain start the service by settings the rights via GPO. I have eaten my brains out to fix this, but Windows' error system isn't all that great (I'm used to work with Debian).
Anyway, here is the solution that worked for me:
I checked the output from "sc sdshow vss" with an healthy PC. The output was not the same on 2 broken machines compared with each other and compared against the healthy PC.
I put the correct settings to it using:
sc sdset vss D:(A, , CCLCSWRPWPDTLOCRRC, , , SY)(A, , CCDCLCSWRPWPDTLOCRSDRCWDWO, , , BA)(A, , CCLCSWLOCRRC, , , AU)(A, , CCLCSWRPWPDTLOCRRC, , , PU)
(This also is the correct key)
If your output is the same, then this is not your fix, sorry.