Sorry for bringing up an old post, but this came up in my search and I just wanted to add to the explanation here.
You can test the SSL certificate for any site here: https://www.ssllabs.com/ssltest/analyze.html. If the Certification Paths indicates that one of the certificates required an "extra download", then that is an indication that the remote site did not properly include all certificates in the chain in their SSL Handshake.
For example, I was having problems with https://www.cisco-global-returns.com.
In the Certification Paths section, we can see that the server did not provide the full certificate chain as it should (Sent by server). You can see that the certificate USERTrust RSA Certification Authority was not sent by the server, so the testing site had to download the certificate.
While this is technically a problem with the configuration at the remote site, users will be frustrated that the site works properly when browsed from networks not under Palo Alto SSL Decryption. To work around this problem, you can import the missing Intermediate certificate into your firewall. Note however, that you will now take responsibility for ensuring that the certificate you just imported has not been revoked, so use your best judgement here.
Directions for importing an Intermediate Cert: https://live.paloaltonetworks.com/t5/Management-Articles/How-to-Import-the-Intermediate-CA-on-the-Fi...
