I was trying to get some Ubuntu PGP Key’s for some ppa.launchpad.net sources, and apt-key kept erroring out. All I had to do was open up 11371 on my firewall or just use http://keyserver.ubuntu.com:80 which would force the HTTP protocal instead of HKP.
It’s that simple actually.
http://superuser.com/questions/64922/how-to-work-around-blocked-outbound-hkp-port-for-apt-keys