Indeed a certificate was missing, not a root certificate but an intermediate certificate. HTTPS servers are supposed to send all certs in the chain (minus the root) with their response, but some servers don't. Web browsers can cope with this by using a technique called AIA (Authority Information Access) chasing*, however many other clients don't implement this.
As Steffen Ulrich mentioned in his comment, you can find the missing certificate and install it on your system.
First get the certificate. You can do it manually by checking the site on SSLLabs, and googling the fingerprint of the missing cert. The certificate should be in PEM format (base64 encoded with BEGIN and END CERTIFICATE). I've also written a script to fetch the certificate via AIA before I realized one can do it manually: https://github.com/jdmansour/fetch-intermediate-certs
Then, to import the cert on Ubuntu/Debian, place it into /usr/share/ca-certificates/extra
(create the directory if neccessary) and run sudo dpkg-reconfigure ca-certificates
. It will ask you if it should trust new certificates on system updates - choose any option you like, I think "yes" is the default. In the next screen, you can enable your new certificate. It should be picked up by most tools that use OpenSSL immediately.
*) As far as I know, Firefox doesn't implement AIA, but it somehow works there too.