Unable to Send Pgp Key to Keyserver

Trying to follow the steps in to create a deb package for some software...

I had to start by generating a GPG key

$ gpg --gen-key

Then upload the public part of your key to a keyserver

$ gpg --send-keys --keyserver keyserver.ubuntu.com 12345678
gpg: sending key 12345678 to hkp server keyserver.ubuntu.com
gpg: keyserver timed out
gpg: keyserver send failed: keyserver error

Tried to add port 80 because I read something about firewall blocking these requests

gpg --send-keys --keyserver hkp://keyserver.ubuntu.com:80 C58C1F62
gpg: sending key C58C1F62 to keyserver.ubuntu.com:80
gpgkeys: no keyserver host provided
gpg: keyserver internal error
gpg: keyserver send failed: keyserver error

Tried other servers that I found searching for these errors on the net

$ gpg --send-keys --keyserver sks-keyservers.net:80 12345678
gpg: sending key 12345678 to keyserver.sks-keyservers.net:80
gpgkeys: no keyserver host provided
gpg: keyserver internal error
gpg: keyserver send failed: keyserver error

$ gpg --send-keys --keyserver  pgp.mit.edu:80 12345678
gpg: sending key 12345678 to pgp.mit.edu:80
gpgkeys: no keyserver host provided
gpg: keyserver internal error
gpg: keyserver send failed: keyserver error

also tried

gpg --send-keys --keyserver  keyserver.pgp.com:80 12345678
gpg --send-keys --keyserver  keyserver.sks-keyservers.net:80 12345678

(just in case I needed the "keyserver" thing)

All with the same error.

What am I missing ?

Update: Changed option order and added hkp:\ protocol - and I am still back where I started - with a slight improvement in the message

$ gpg --keyserver hkp://pool.sks-keyservers.net --send-keys 12345678
  gpg: sending key 12345678to hkp server pool.sks-keyservers.net
  gpg: keyserver timed out
  gpg: keyserver send failed: keyserver error

Edit: I read that the missing keyserver host may be a wrong message, actually meaning that the key does not exist on the server... But If I send it, of course it would not exist.

gpg --send-keys --keyserver keyserver.ubuntu.com:80 C58C1F62
gpg: sending key C58C1F62 to keyserver.ubuntu.com:80
gpgkeys: no keyserver host provided
gpg: keyserver internal error
gpg: keyserver send failed: keyserver error

dig keyserver.ubuntu.com
; <<>> DiG 9.8.1-P1 <<>> keyserver.ubuntu.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 40676
;; flags: qr rd ra; QUERY: 1, ANSWER: 2, AUTHORITY: 0, ADDITIONAL: 0    
;; QUESTION SECTION:
;keyserver.ubuntu.com.      IN  A    
;; ANSWER SECTION:
keyserver.ubuntu.com.   217 IN  A   91.189.90.55
keyserver.ubuntu.com.   217 IN  A   91.189.89.49    
;; Query time: 1 msec
;; SERVER: 127.0.0.1#53(127.0.0.1)
;; WHEN: Tue Sep 30 12:41:52 2014
;; MSG SIZE  rcvd: 70

which means the server exists ? But the QUESTION SECTION looks empty...

gpg --send-keys --keyserver hkp://keyserver.ubuntu.com:80 C58C1F62
gpg: sending key C58C1F62 to hkp server keyserver.ubuntu.com
gpgkeys: HTTP post error 7: couldn't connect: eof
gpg: keyserver internal error
gpg: keyserver send failed: keyserver error

dig hkp://keyserver.ubuntu.com    
; <<>> DiG 9.8.1-P1 <<>> hkp://keyserver.ubuntu.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 968
;; flags: qr rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 0

;; QUESTION SECTION:
;hkp://keyserver.ubuntu.com.    IN  A    
;; AUTHORITY SECTION:
ubuntu.com.     899 IN  SOA ns1.canonical.com. hostmaster.canonical.com. 2014093001 10800 3600 604800 3600    
;; Query time: 164 msec
;; SERVER: 127.0.0.1#53(127.0.0.1)
;; WHEN: Tue Sep 30 13:08:37 2014
;; MSG SIZE  rcvd: 105

I also tried to add an option for proxy...

gpg --keyserver-options http-proxy=' --keyserver hkp://keyserver.ubuntu.com:80 --send-keys C58C1F62
gpg: sending key C58C1F62 to hkp server keyserver.ubuntu.com
gpgkeys: HTTP post error 7: couldn't connect: eof
gpg: keyserver internal error
gpg: keyserver send failed: keyserver error