It is not clear from the error that you were missing libsodium. I don't remember what was my error anyway, I'll try again later. But I can't even find libsodium on my apt.
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.
