|There's more than one way to do things|
So I've been running into this same problem and it's been driving me nuts. I'm replying to this since my search is turning this node up and maybe this will help other people.
The actual answer is that your problem is specific to this Verisign certificate, for
Note that you are in fact getting certificates back from the server; your openssl output has "BEGIN CERTIFICATE" in it after all. What is failing is the certificate chain verification because the Mozilla root certificate bundle that everybody uses has two distinct versions of the same root certificate, i.e., same issuer identity, same public key being advertised, different signature algorithms, MD2 (very old, long-obsolete) vs. SHA1 (still has a few years left, though NIST is getting nervous about this one, too). Verisign is evidently embarrassed by having MD2-signed certificates still out in the wild, would like them to go away, but they can't quite yet, so they've requested that Mozilla distribute both versions of the certificate.
The problem is that Debian's certificate store — and I'm guessing this applies to everyone who uses openssl to manage certificates — currently can't deal with multiple certificates having the same name, so they're just installing the one with the more secure signature, but the server you're talking to is sending you a chain that ends at the MD2-signed root, which you don't have installed, hence fail.
You can check if you have this problem (if you're using Debian and it's still May of 2013, then you do) by downloading Mozilla::CA from CPAN, grepping through its certificate file for "Class 3 Public Primary Certification Authority" (without any "Gn" suffix); find both versions — see which one is the MD2-signed one by running them through openssl x509 -text — or (better) run them through
to see which one isn't properly installed (substitute your own -CApath or -CAfile as necessary; make sure you've got the right one by verifying some of the other certificates).
My way out of the box is to just install the missing MD2 certificate in your /usr/local/share/ca-certificates and rerun update-ca-certificates. Maybe also do this for "Startcom Certification Authority" which is also duplicated in the same way (they upgraded their sig from SHA1 to SHA256). The problem with this is if Mozilla ever decides to remove these certificates, you won't find out so you'll want to leave a note for yourself for two years from now to check to see if it's still in the Mozilla bundle or if Debian has finally fixed the bug referenced below
Or you could activate CRL (certificate revocation list) checking (I need to figure out how to do that...)
Note that this is still a valid root certificate; Mozilla still includes it in its bundle and will probably continue to do so until the last servers using it finally upgrade. They're just not absolutely certain there isn't some way of exploiting the known weaknesses in MD2 (nobody's found one yet) -- my understanding is you still have to break RSA in order to forge a fake certificate chain and the real question is how much longer 1024-bit keys will be viable, and presumably if that ever becomes a problem, there'll be a mass certificate revocation with considerable fanfare... knock wood.http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=683403