> Could you show the result of
> 
> curl -Iv https://cloud-images.ubuntu.com/query/precise/server/released-
> dl.current.txt
 
This is the result:
curl -Iv https://cloud-images.ubuntu.com/query/precise/server/released-dl.current.txt
* About to connect() to cloud-images.ubuntu.com port 443 (#0)
*   Trying 91.189.88.141... 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.

I looked into synaptic and ca-certificates and ca-certificates-java are installed.
I also verified that all installed the files are there and everything was in place.
After that i reinstalled both packages and after that it worked:

* About to connect() to cloud-images.ubuntu.com port 443 (#0)
*   Trying 91.189.88.141... 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 handshake, Server key exchange (12):
* 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 DHE-RSA-AES256-SHA
* Server certificate:
*      subject: O=cloud-images.ubuntu.com; OU=Domain Control Validated; CN=cloud-images.ubuntu.com
*      start date: 2012-07-12 13:57:09 GMT
*      expire date: 2013-07-14 07:49:21 GMT
*      subjectAltName: cloud-images.ubuntu.com matched
*      issuer: C=US; ST=Arizona; L=Scottsdale; O=GoDaddy.com, Inc.; OU=http://certificates.godaddy.com/repository; CN=Go Daddy Secure Certification Authority; serialNumber=07969287
*      SSL certificate verify ok.
> HEAD /query/precise/server/released-dl.current.txt HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0 OpenSSL/1.0.1 zlib/1.2.3.4 libidn/1.23 librtmp/2.3
> Host: cloud-images.ubuntu.com
> Accept: */*
> 
< HTTP/1.1 200 OK
HTTP/1.1 200 OK
< Date: Mon, 10 Jun 2013 06:08:15 GMT
Date: Mon, 10 Jun 2013 06:08:15 GMT
< Server: Apache/2.2.14 (Ubuntu)
Server: Apache/2.2.14 (Ubuntu)
< Last-Modified: Mon, 03 Jun 2013 15:09:15 GMT
Last-Modified: Mon, 03 Jun 2013 15:09:15 GMT
< ETag: "29c013b-1e9-4de41590b5cc0"
ETag: "29c013b-1e9-4de41590b5cc0"
< Accept-Ranges: bytes
Accept-Ranges: bytes
< Content-Length: 489
Content-Length: 489
< Vary: Accept-Encoding
Vary: Accept-Encoding
< Content-Type: text/plain
Content-Type: text/plain

< 
* Connection #0 to host cloud-images.ubuntu.com left intact
* Closing connection #0
* SSLv3, TLS alert, Client hello (1):

Is there any kind of cache or something that gets refreshed after a reinstall?
As i have written before, all installed files were in place.