Starting with the release of Windows Vista, the default list of Certificate Authorities that get included in the Windows Trusted Root Certificate store has been reduced in order to increase performance while validating certificates. Certificate authorities submit their requests for inclusion to Microsoft through the "Microsoft Root Certificate Program". During certificate validation, if the certificate chain leads to a root CA that is not found in the trusted root certificate store but it is in the root program, Windows will automatically download and install the root CA in real-time without prompting the user, thereby completing the chain up to the trusted root CA.
Refer to http://netsekure.org/2011/04/automatic-ca-root-certificate-updates-on-windows/
for more details.
This process is also used during certificate verification with PSAL, however, in some cases, the detection of the missing root CA by PSAL occurs before Windows is done downloading and installing the trusted Root CA in the user's certificate store which causes the security warning to be generated by PSAL. Once the certificate is installed, PSAL will use the root CA to validate the certificate chain and will no longer display the security warning.