I've had this happen before a few years ago but I cant remember exactly how I fixed it :(
A fresh Windows 8.1 install (don't ask !) and it wont run Windows Update at all. Sits there for a while and eventually returns an error around a wincatalog or something. I should have written it down.
IIRC the fix was a Windows Update Agent/Client rollup or something, and possibly only the March 2016 version worked, but I've tried that and after running overnight it fails with a non-descriptive error.
Google turns up a million options, most of which are just garbage.
I've restarted the BITS and WU services, rebooted, tried the Windows Agent rollup for 8.1 but nothing works so far.
Anyone else seen this before or have any ideas ?