I'm running Kubuntu 12.04 and trying to update it. I've again been hit by a problem I had a year ago that's never been solved, illustrated by this:
The problem is not with the choice of keyserver; I've tried several, all with the same behavior. I've opened port 11371, which some people thought might be the problem. And I can ping any of the keyservers, so the "Host not found" message is bogus. Apparently the line I quoted works for some people but not for others (like me). I can painfully get the key by going to the site and retrieving it directly and then installing it explicitly, but that's hardly a satisfactory solution, particularly when I have to get several keys.
pwa@pwa-K60IJ:~/Documents$ gpg --keyserver hkp://subkeys.pgp.net --recv-keys A8AA1FAA3F055C03
gpg: requesting key 3F055C03 from hkp server subkeys.pgp.net
?: subkeys.pgp.net: Host not found
gpgkeys: HTTP fetch error 7: couldn't connect: Success
gpg: no valid OpenPGP data found.
gpg: Total number processed: 0