SSL Certificate error in Internet Explorer but not Firefox, Chrome or Edge

Question

I have installed security certificates on 2 websites, which work perfectly in Firefox, Chrome and Edge but when accessing in Internet Explorer (10 and 11), users get the "There is a problem with this website’s security certificate." page with the following errors:

The security certificate presented by this website was not issued by a trusted certificate authority.

The security certificate presented by this website was issued for a different website's address.

If the user clicks "Continue" or reloads, the page loads fine and the top bar is green with no errors reported. As you will see in the images, all appears to be good. If there truly was a problem, I would expect the top bar to be red.

I have checked the site on whynopadlock.com and no errors were reported

Qualys SSL test gives the site an A+ rating:

• The relevant Starfield Certification Authorities are all in the certificate manager and trusted.
• There are no elements on the page that are accessed via insecure channels.
• The domain exactly matches the one on the certificate.
• The certificate is in date and not revoked.
• The time on the computers and server are all correct.
• Tried on different computers in different networks. Same result.

I also have the same problem on a different domain, on a different server with a different certificate authority (Let's Encrypt). All details are correct as above and it works in other browsers, but not IE.

The web servers are both CentOS7 running Plesk 12.5.

I am at a loss as to what to try next.