VeriSign Class 3 certificate not trusted by Windows?

I distribute a Windows desktop app which has all executable files digitally signed by a Verisign Class 3 Code Signing certificate. For the vast majority of users, this seems to work fine.

However a small number of users report the certificate is invalid. They say it comes up with the message "A certificate chain processed, but terminated in a root certificate which is not trusted by the trust provider". This corresponds to error code CERT_E_UNTRUSTEDROOT (0x800B0109). This has also been reported on a fully-updated Windows 7 machine. So presumably my certificate is OK, but Windows sometimes doesn't trust VeriSign certificates.

Why does Windows sometimes not trust VeriSign? Is there anything I can add to my installer (also signed) which will tell Windows to trust the certificate?

There are frequent updates of the Root Certificates which Microsoft rolls out via Windows Update, but which are tagged as "optional update". Hence not all users may have them installed and may need to install them manually. This also holds for "fully updated" machines, as the automatic installation is often set to only install "important updates", which the Root Certificate updates are not.

Depending on the type of desktop application, you may have to follow certain rules when signing, too. For example applications interacting with the Windows Security Center require essentially the same signing method as drivers. That is, the certificate chain gets embedded along with the signature (/ac switch to signtool). You can get the MSCV-VSClass3.cer applicable to VeriSign certificates here.

The process is often called cross-signing, which seems to be a misnomer. While this is one step in getting your driver binary or catalog cross-signed, the vital step is that Microsoft signs the driver (or more usually the catalog file these days), which is the actual cross-signing.