Funciona para mim (mesma versão do GnuPG). Provavelmente seu cliente HTTP de alguma forma mexeu nos arquivos. Tente usar o wget que usei.
wget http://download.dnscrypt.org/libsodium/releases/libsodium-0.2.tar.gz
wget http://download.dnscrypt.org/libsodium/releases/libsodium-0.2.tar.gz.sig
gpg --verify libsodium-0.2.tar.gz.sig