The patch itself is installed by Windows and part of the install could be a digital signature check. What does the windowsupdate.log show on the client machine?
addTargetedserviceMapping 1E769F1E-a3f7-47F2-BBE1-9274E4EDDB19-> 3DA21691-E39D-4DA6-8A4B-B43877BCB1B7
agent warning: could not delete software\Microsoft\windows\currentversion\windowsupdate\service\1e769f1e-a3f7-47f2-bbe1-9274e4eddb19 service registry key 0x800070002
agent warning; failed to delet service fro the backup store error 0x80070002
agent removeTargetedserviceMapping 1E.....
If I manually try to install I see
C:\cd558873a39597071043f8765785\NDP46-kb3143693.msp Signature could not be verified for NDP46-kb3143693.msp
No filehash provided. cannot perform filehash verification for NDP46-kb3143693.msp
file NDP46...c:\cd5588...failed authentication.(Error=-2146762486) it is recommended that you delete this file and retry setup again.....
I did and it did the same..
If running the patch by hand give the same error, it may be best to contact MS support. From what I see in my google searches, the most common recommendation is to "Download the latest root certificates from Microsoft for your operating system.". This would leave me to believe your root certificates are out of date therefore the OS is unable to verify the digital signature of the file. I believe the root certificates are updated when Windows Update performs patching. There may be other methods to update the root certificate, I think this is the official MS page for it: Configure Trusted Roots and Disallowed Certificates