It it helps, I set gnutls log level to 1 and go the following, which makes me think the issue is a server issue
Importing package-keyring.gpg...done
Contacting host:
elpa.gnu.org:443gnutls.c: [1] (Emacs) connecting to host:
elpa.gnu.orggnutls.c: [1] (Emacs) allocating credentials
gnutls.c: [1] (Emacs) setting the trustfile: /etc/ssl/certs/ca-certificates.crt
gnutls.c: [1] (Emacs) gnutls callbacks
gnutls.c: [1] (Emacs) gnutls_init
gnutls.c: [1] (Emacs) got non-default priority string: NORMAL:%DUMBFW
gnutls.c: [1] (Emacs) setting the priority string
gnutls.c: [audit] Note that the security level of the Diffie-Hellman key exchange has been lowered to 256 bits and this may allow decryption of the session data
gnutls.c: [1] (Emacs) non-fatal error: Resource temporarily unavailable, try again. [2666 times]