It is well reported that problems can be experienced during the installation of KB2919355 for Windows 8.1. This is a 'must have' update as it will be a pre-requisite for installing future updates.

I was one of the unlucky ones that experienced error 80073712 when attempting to install this update. The issue seems to be a conflict with this update and other updates which are already installed. The way I got around this which may be of interest was:

I rolled back the OS so that the last updates I had installed were from March. I then downloaded from the Microsoft download site (rather than using 'Update Windows') the update KB2919355 together with updates KB2919442, KB29329046, KB2937592, KB2938439 and KB2934018. I then installed then in the order:

rebooting after each install when required.

I then used 'Update Windows' to install the remaining updates. This process enabled me to install all the updates successfully.