Parece que o libsodium-0.6.0 make install não executa ldconfig para atualizar o cache do vinculador. Execute sudo ldconfig (ou sudo ldconfig -v ) e tente novamente.
Eu limpei tudo com make clean nas pastas libsodium e zeromq, depois reinstaleleid libsodium-0.6.0 e zeromq-4.1.2.
libsodium parece estar instalado OK, mas a instalação do zeromq falhou em make check com inúmeros erros reclamando de não encontrar libsodium.so.10 parecido com:
/home/user/sources/zeromq-4.1.2/.libs/lt-test_sub_forward: error while loading shared libraries: libsodium.so.10: cannot open shared object file: No such file or directory
FAIL: test_sub_forward
Parece que o libsodium-0.6.0 make install não executa ldconfig para atualizar o cache do vinculador. Execute sudo ldconfig (ou sudo ldconfig -v ) e tente novamente.