At work we’re pretty heavily firewalled. This means that outbound requests on funny ports are often firewalled off, and systems that rely on such ports will time out.
One such system that is commonly used yet inaccessible is the GPG SKS port 11371. And many many Linux things use GPG!
What got me looking was the common command to import a key, in this case for Spotify.
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 94558F59
It will time out and fail to import the key, subsequently causing your apt-get operations to fail. A quick update to the command cures it. You *have* to specify hkp:// and :80
sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 94558F59
Success! You can also apply the same changes to your default keyservers in ~/.gnupg/gpg.conf