Gente, consegui resolver, com uma ajuda do pessoal da documentação lá no canal do irc.
O problema era que o o Keyserver não estava especificado. Foi preciso especificá-lo no comando de envio, usando o comando --keyserver.
Fica assim a linha de Comando, especificando o keyserver como keyserver.ubuntu.com:
$ gpg --keyserver keyserver.ubuntu.com --send-key [Key ID]
Deixo ai a resolução pra se mais alguém precisar.
Té mais
=)