Information below on the Remote Site's old working certicate, new/renewed failing certificate and exception.
No other change on the SF side or Remote Site.
---------------------------------------------------------------------
Root certificate IS THE SAME FOR BOTH, the old and new/renewed certificates:
  CN = VeriSign Class 3 Public Primary Certification Authority - G5
  OU = (c) 2006 VeriSign, Inc. - For authorized use only
  OU = VeriSign Trust Network
  O = VeriSign, Inc.
  C = US
Thumbprint 4e b6 d5 78 49 9b 1c cf 5f 58 1e ad 56 be 3d 9b 67 44 a5 e5
  ----------------------
The above root certificate seems to be the same as in SF Outbound Messaging SSL CA Certificates:
https://developer.salesforce.com/page/Outbound_Messaging_SSL_CA_Certificates#verisignclass3g5ca
  • 105 verisignclass3g5ca
Owner: CN=VeriSign Class 3 Public Primary Certification Authority - G5,
 OU="(c) 2006 VeriSign, Inc. - For authorized use only",
 OU=VeriSign Trust Network,
 O="VeriSign, Inc.",
 C=US
Issuer: CN=VeriSign Class 3 Public Primary Certification Authority - G5,
 OU="(c) 2006 VeriSign,
 Inc. - For authorized use only",
 OU=VeriSign Trust Network,
 O="VeriSign, Inc.",
 C=US
Serial number: 18dad19e267de8bb4a2158cdcc6b3b4a
Valid from: Tue Nov 07 16:00:00 PST 2006 until: Wed Jul 16 16:59:59 PDT 2036
Certificate fingerprints:
  MD5:  CB:17:E4:31:67:3E:E2:09:FE:45:57:93:F3:0A:FA:1C
  SHA1: 4E:B6:D5:78:49:9B:1C:CF:5F:58:1E:AD:56:BE:3D:9B:67:44:A5:E5
  Signature algorithm name: SHA1withRSA
  Version: 3
---------------------------------------------------------------------
However, the intermediate certificate issuers are different:

Remote Site's old certicate that worked with intermediate issuer:
CN = VeriSign Class 3 International Server CA - G3
OU = Terms of use at https://www.verisign.com/rpa (c)10
OU = VeriSign Trust Network
O = VeriSign, Inc.
C = US

Remote Site's new, renewed certicate that fails with intermediate issuer:
CN = Symantec Class 3 Secure Server CA - G4
OU = Symantec Trust Network
O = Symantec Corporation
C = US
---------------------------------------------------------------------
Remote Site's new, renewed certicate exception in SF:
Exception:
https://...
sun.security.validator.ValidatorException:
PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException:
unable to find valid certification path to requested target

Many thanks in advance.