In order to use the gnewpg key server, you have to configure your PGP client to trust the CAcert root certificate. See CAcert’s manual on how to do this. Alternatively, you might disable encryption by replacing hkps:// with hkp:// in the keyserver URL. Note that this is insecure, as other people might spoof your keyring, especially if you are on a wireless connection.