I don't know exactly why this solution won't work for you, there could be a number of issues at play here.

In short, try this:

1. Reset all your 'tls 'nsm and 'gnutls customize options to their defaults.

2. $ rm -rf ~/.emacs.d/network-security.data

3. Install https://github.com/antifuchs/safe-tls-defaults-mode/blob/mas...

This nice gentlement packaged up the settings I suggested on a Reddit thread. It should work most of the time, if not, you can adjust the CLI string.