Replicant

It works for me too:

gpg --recv-key 4A80EB23 
gpg: requesting key 4A80EB23 from hkp server keys.gnupg.net
gpg: key 4A80EB23: "Replicant project release key <contact@replicant.us>" not changed
gpg: Total number processed: 1
h3. gpg:              unchanged: 1

Fil, you might need to try a command which selects a different key sever:

gpg --keyserver pgp.mit.edu --recv-key 4A80EB23
gpg: requesting key 4A80EB23 from hkp server pgp.mit.edu
gpg: key 4A80EB23: "Replicant project release key <contact@replicant.us>" not changed
gpg: Total number processed: 1
gpg:              unchanged: 1

Using the web interface of pgp.mit.edu:

http://pgp.mit.edu/pks/lookup?op=vindex&search=0x16D1FEEE4A80EB23

you can copy the key in a local file replicant.pub:

http://pgp.mit.edu/pks/lookup?op=get&search=0x16D1FEEE4A80EB23

and import it in your key ring:

gpg --import replicant.pub
gpg: key 4A80EB23: "Replicant project release key <contact@replicant.us>" not changed
gpg: Total number processed: 1
gpg:              unchanged: 1

PS To help you, I'm also attaching the replicant.pub here, you can compare it with the one from the key server and use it if it's the same.

Closing since it appears to be a transient error from the server:

$ gpg --keyserver keys.gnupg.net --recv-key 4A80EB23
gpg: requesting key 4A80EB23 from hkp server keys.gnupg.net
gpg: key 4A80EB23: public key "Replicant project release key <contact@replicant.us>" imported
gpg: 3 marginal(s) needed, 1 complete(s) needed, classic trust model
gpg: depth: 0  valid:   2  signed:  63  trust: 0-, 0q, 0n, 0m, 0f, 2u
gpg: depth: 1  valid:  63  signed: 358  trust: 21-, 10q, 6n, 12m, 14f, 0u
gpg: depth: 2  valid: 164  signed: 479  trust: 150-, 2q, 2n, 6m, 4f, 0u
gpg: depth: 3  valid:   4  signed:  16  trust: 4-, 0q, 0n, 0m, 0f, 0u
gpg: next trustdb check due at 2016-10-26
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)