Another potential problem is that gnutls-cli, which Emacs may be trying to use to initiate the TLS connection, just may not be installed. Unfortunately, if this is the case, the error message produced by Emacs gives no indication of this. If this is indeed the problem, then on a Debian-like system you need to install gnutls-bin, whereas on a RedHat-like ...
I had the same problem. It seems like gpg is not able to locate a key server.
To fix it, in the ~/.emacs.d/elpa/gnupg directory, create a file named gpg.conf with the following line:
Then run this on the command line:
gpg --homedir ~/.emacs.d/elpa/gnupg --receive-keys 066DAFCB81E42C40
And then in emacs: