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 94558F59
gpg: requesting key 94558F59 from hkp server keyserver.ubuntu.com
gpg: keyserver timed out
gpg: keyserver receive failed: keyserver error

To force gpg to download the key on port 80, change the --keyserver parameter accordingly:

gpg --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 94558F59