CONCLUSION
Manual repair was NOT successful. After exhausting MANY MANY routes, including one-by-one installs, found to be down to the Software Protection Service not wanting to start - at all. This was NOT fixed by a "Refresh" within Windows 8, nor was it fixed by off-line SFC or by DISM /cleanup (when I eventually got it to work).
Solution was to burn a Windows 8 DVD, run Setup, and then run an installation and remove ALL applications, leaving only User Data (second option).
After this, all updates installed correctly, and no software I have installed subsequently has brought the problem back.
Ie - there is NO FIX for my issue of the Software Protection Service failing.
To see if this is your issue too, go:
Start --> type "Services" (or Windows Key + R --> services.msc)
Scroll down to find Software Protection.
It will be stopped.
attempt to start it by double-clicking and clicking Start.
I get an Access Denied error.
I tried a myriad of fixes, over many MANY days, and in the end concluded that the amount of time it was taking me exceeded the amount of time it would take me to copy off all my data to an external HDD and re-install all my applications.
I recommend that you just do to the same.