There should be pub key that has to be imported. In general the keyserver could fail.
Here a different server: SKS Keyservers: Overview of the pools
you could do:
gpg --keyserver pool.sks-keyservers.net --recv-keys <key>
or permanent:
echo "keyserver hkp://pool.sks-keyservers.net" > /home/$USER/.gnupg/gpg.conf
an then:
gpg --recv-keys <key>