Yes, it is problem with certificates, Ubuntu and Debian seem to provide outdated certs.
I found a different fix that doesn't need any patches to location-proxy. The latest maemo-security-certman tree contains that fix which is now working just fine on the N900 sitting in front of me. Nice fast GPS lock. The fix involves putting the old insecure VeriSign certificate into a separate certificate store that location-proxy will load but that microb and other things wont. This is with supl.nokia.com btw.