Comment 38 for bug 435193

Please ask your administrator to open tcp/11371 port on your firewall. I had also this trouble till that port was opened. After was opened it worked fine. Just try to open http://keyserver.ubuntu.com:11371/ on your browser to check it.