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