There does appear to be an issue with 12.04.

From a 10.04 server:

=========================================================================
# strace -o /tmp/foo.out curl -Iv https://test.sagepay.com
* About to connect() to test.sagepay.com port 443 (#0)
*   Trying 195.170.169.8... connected
* Connected to test.sagepay.com (195.170.169.8) port 443 (#0)
* successfully set certificate verify locations:
*   CAfile: none
  CApath: /etc/ssl/certs
* SSLv3, TLS handshake, Client hello (1):
* SSLv3, TLS handshake, Server hello (2):
* SSLv3, TLS handshake, CERT (11):
* SSLv3, TLS handshake, Server finished (14):
* SSLv3, TLS handshake, Client key exchange (16):
* SSLv3, TLS change cipher, Client hello (1):
* SSLv3, TLS handshake, Finished (20):
* SSLv3, TLS change cipher, Client hello (1):
* SSLv3, TLS handshake, Finished (20):
* SSL connection using RC4-MD5
* Server certificate:
*        subject: 1.3.6.1.4.1.311.60.2.1.3=GB; 2.5.4.15=Private Organization; serialNumber=01045967; C=GB; ST=TYNE AND WEAR; L=Newcastle Upon Tyne; O=Sage (UK) Limited; OU=Sage; OU=Terms of use at www.verisign.co.uk/rpa (c)05; OU=Authenticated by VeriSign; OU=Member, VeriS
*        start date: 2011-02-01 00:00:00 GMT
*        expire date: 2013-01-31 23:59:59 GMT
*        common name: test.sagepay.com (matched)
*        issuer: C=US; O=VeriSign, Inc.; OU=VeriSign Trust Network; OU=Terms of use at https://www.verisign.com/rpa (c)06; CN=VeriSign Class 3 Extended Validation SSL SGC CA
*        SSL certificate verify ok.
> HEAD / HTTP/1.1
> User-Agent: curl/7.19.7 (i486-pc-linux-gnu) libcurl/7.19.7 OpenSSL/0.9.8k zlib/1.2.3.3 libidn/1.15
> Host: test.sagepay.com
> Accept: */*
>
< HTTP/1.1 200 OK
HTTP/1.1 200 OK
< Date: Thu, 16 Aug 2012 10:56:46 GMT
Date: Thu, 16 Aug 2012 10:56:46 GMT
< Server: Microsoft-IIS/6.0
Server: Microsoft-IIS/6.0
< P3P: CP="CUR"
P3P: CP="CUR"
< X-Powered-By: ASP.NET
X-Powered-By: ASP.NET
< Content-Length: 1397
Content-Length: 1397
< Content-Type: text/html
Content-Type: text/html
< Set-Cookie: ASPSESSIONIDCUDDCSTT=JOANLLECHFAFLAGOCJGBIFPI; secure; path=/
Set-Cookie: ASPSESSIONIDCUDDCSTT=JOANLLECHFAFLAGOCJGBIFPI; secure; path=/
< Cache-control: private
Cache-control: private

<
* Connection #0 to host test.sagepay.com left intact
* Closing connection #0
* SSLv3, TLS alert, Client hello (1):

# grep ssl /tmp/foo.out
open("/lib/i686/cmov/libssl.so.0.9.8", O_RDONLY) = 3
stat64("/etc/ssl/certs/7651b327.0", {st_mode=S_IFREG|0644, st_size=834, ...}) = 0
open("/etc/ssl/certs/7651b327.0", O_RDONLY|O_LARGEFILE) = 4
stat64("/etc/ssl/certs/7651b327.1", 0xbfcb697c) = -1 ENOENT (No such file or directory)

# readlink -f /etc/ssl/certs/7651b327.0
/usr/share/ca-certificates/mozilla/Verisign_Class_3_Public_Primary_Certification_Authority.crt
==================================================================

And then the result from 12.04 (tested on two different servers have ca-certificates installed):

==================================================================

# strace -o /tmp/foo.out curl -Iv https://test.sagepay.com
* About to connect() to test.sagepay.com port 443 (#0)
*   Trying 195.170.169.8... connected
* successfully set certificate verify locations:
*   CAfile: none
  CApath: /etc/ssl/certs
* SSLv3, TLS handshake, Client hello (1):
* SSLv3, TLS handshake, Server hello (2):
* SSLv3, TLS handshake, CERT (11):
* SSLv3, TLS alert, Server hello (2):
* SSL certificate problem, verify that the CA cert is OK. Details:
error:14090086:SSL routines:SSL3_GET_SERVER_CERTIFICATE:certificate verify failed
* Closing connection #0
curl: (60) SSL certificate problem, verify that the CA cert is OK. Details:
error:14090086:SSL routines:SSL3_GET_SERVER_CERTIFICATE:certificate verify failed
More details here: http://curl.haxx.se/docs/sslcerts.html

curl performs SSL certificate verification by default, using a "bundle"
 of Certificate Authority (CA) public keys (CA certs). If the default
 bundle file isn't adequate, you can specify an alternate file
 using the --cacert option.
If this HTTPS server uses a certificate signed by a CA represented in
 the bundle, the certificate verification probably failed due to a
 problem with the certificate (it might be expired, or the name might
 not match the domain name in the URL).
If you'd like to turn off curl's verification of the certificate, use
 the -k (or --insecure) option.

# grep ssl /tmp/foo.out
open("/lib/i386-linux-gnu/libssl.so.1.0.0", O_RDONLY|O_CLOEXEC) = 3
stat64("/etc/ssl/certs/415660c1.0", {st_mode=S_IFREG|0644, st_size=834, ...}) = 0
open("/etc/ssl/certs/415660c1.0", O_RDONLY|O_LARGEFILE) = 4
stat64("/etc/ssl/certs/415660c1.1", 0xbfa88f30) = -1 ENOENT (No such file or directory)

# readlink /etc/ssl/certs/415660c1.0
Verisign_Class_3_Public_Primary_Certification_Authority.pem
================================================================