You may be running a distro that doesn't have libsodium (such as ubuntu 14). In this case you have to grab libsodium manually and build et from source.