If you get a keyserver time out when trying to download a public key from a public GPG server, you may need to check your firewall settings. When receiving a public key, gpg connects to TCP port 11371, which not commonly opened up when you are behind a strict firewall. Luckily, most key servers also listen on port 80, allowing to get the public keys through that port.
When attempting to download a key and you are not able to connect to the default port, you will get something like:
gpg --keyserver keyserver.ubuntu.com --recv-keys 94558F59gpg: requesting key 94558F59 from hkp server keyserver.ubuntu.comgpg: keyserver timed outgpg: keyserver receive failed: keyserver error