Something is rendering receiving keys from keyserver.ubuntu.com impossible and I'm not even sure where to begin in trying to resolve this.
As an example, we'll use the Spotify linux app found here: http://www.spotify.com/us/download/previews/
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 4E9CFF4E
Executing: gpg --ignore-time-conflict --no-options --no-default-keyring --secret-keyring /etc/apt/secring.gpg --trustdb-name /etc/apt/trustdb.gpg --keyring /etc/apt/trusted.gpg --primary-keyring /etc/apt/trusted.gpg --keyserver keyserver.ubuntu.com --recv-keys 4E9CFF4E
gpg: requesting key 4E9CFF4E from hkp server keyserver.ubuntu.com
gpg: keyserver timed out
gpg: keyserver receive failed: keyserver error
To be clear, though, this has nothing to do with Spotify. The same result comes from every one of my attempts to grab keys from ubuntu. There is something wrong on my side. As always, any help in tracking this down would be appreciated.
Prior to submitting this, I've discovered that the problem is with my DNS and/or router. Currently I have my router configured to use Google DNS (8.8.8.8 / 8.8.4.4) and in my router logs I'm receiving a flood of DNS errors. The following is an excerpt:
(GMT-06:00)02:48:10 Tue Sep 06 2011 syslog: failed dns request len=145,srcip=8.8.4.4, url=_pgpkey-http._tcp.keyserver.ubuntu.com
(GMT-06:00)02:48:12 Tue Sep 06 2011 syslog: No response for DNS request to server 68.94.156.1 yet.
(GMT-06:00)02:48:14 Tue Sep 06 2011 syslog: No response for DNS request to server 68.94.157.1 yet.
(GMT-06:00)02:48:14 Tue Sep 06 2011 syslog: failed dns request len=83,srcip=192.168.0.1, url=keyserver.ubuntu.com.domain.actdsltmp
(GMT-06:00)02:48:14 Tue Sep 06 2011 syslog: All DNS servers tried, no response.
(GMT-06:00)02:48:14 Tue Sep 06 2011 syslog: failed dns request len=158,srcip=8.8.4.4, url=keyserver.ubuntu.com.domain.actdsltmp
(GMT-06:00)02:49:02 Tue Sep 06 2011 syslog: failed dns request len=145,srcip=8.8.4.4, url=_pgpkey-http._tcp.keyserver.ubuntu.com
(GMT-06:00)02:49:05 Tue Sep 06 2011 syslog: No response for DNS request to server 68.94.156.1 yet.
(GMT-06:00)02:49:07 Tue Sep 06 2011 syslog: failed dns request len=158,srcip=8.8.4.4, url=keyserver.ubuntu.com.domain.actdsltmp
(GMT-06:00)02:49:08 Tue Sep 06 2011 syslog: No response for DNS request to server 68.94.157.1 yet.
(GMT-06:00)02:49:08 Tue Sep 06 2011 syslog: failed dns request len=83,srcip=192.168.0.1, url=keyserver.ubuntu.com.domain.actdsltmp
(GMT-06:00)02:49:08 Tue Sep 06 2011 syslog: All DNS servers tried, no response.
Very confused. I'm not even sure if I'm posting this on the correct StackExchange site now.
(OP has solved the issue and posted answer as a comment)