Do NOT! run gpg with sudo. You want to import keys into your users key-ring, not root’s.
If that is the case, try a keyserver that operates on a different port:
hkp://keyserver.ubuntu.com:80. (Port 80 is http and should definitely not be blocked.)