If it only occurs for some updates, but others install, it's unlikely to be an issue with your code signing cert.
I've seen the error: "The Subject is not Trusted for the specified action" when a machine's root certificates are out of date, and the machine doesn't trust the installer. Root certs are usually updated via Windows Update/WSUS when updates are installed.
Aside from that, you'll want to ensure your code signing cert is in Trusted Publishers, and Trusted Root Certification Authorities, for the Computer Account. If the certificate was issued from another root certificate, that root certificate needs to be under Trusted Root Certification Authorities on the client, rather than the code signing cert, to ensure the chain is seen as valid.