The problem seems to be a missing VeriSign Class 3 root certificate. I have found a strange description of the problem on the Nokia forum, and a related problem with a signed app. This also means that the GMail application does not work, as it relies on that particular certificate.
What neither of these links tell you, is that it is not too difficult to install the required root certificate yourself.
Simply browse to the page in question on your computer. Click the padlock (or similar) icon to view the certificate. Somewhere in this dialog you should see a "signature chain" or "signature path", and on top of the path/chain should be the missing root certificate. You need to export this to a file. For my Nokia 6500, the DER format worked fine.
Once you have the file, rename it to .crt and place it on a webserver. The webserver must use the following mime type:
Now simply browse to the file in question, using the built-in webbrowser on the phone, and it will ask you to install the certificate. You can remove it again by visiting the security settings via the phone menu.
If you want the VeriSign Class 3 root certificate, you can go to https://mail.google.com, as they have a certificate signed by that root certificate.
You can also try to download the official certificates and find the one you need:
I have not found an online copy that you can download directly from your phone, so I have put one here: http://www.hexad.dk/vs3.crt.
If you use the above link, be sure to validate the certificate, as I provide no guarantees as to the correctnes of the certificate, other than to say "it works for me". If the certificate is somehow compromised, bad guys may be able to manipulate and read secure communication from your device.