If the make instal on nettle succeeded then it’s odd it would indicate not installed. Try sudo ldconfig to refresh the library cache config. I’ve followed that guide repeatedly and never had that happen, it just worked. The only issue I found with it I forgot to mention is when you do the apt install on that huge package list it fails to find package named perf and that can be safely taken out of list.
If all else fails you can try sudo apt-get install nettle-dev
I’m still confirming the validity of this, but on my last test droplet build I installed cmake, glm, nettle and freeglut from packages vs compiling with no ill effect. GNUtls seemed to be too different in available version so I built from source. It’s a pretty tricky build, and I’m starting to think going the packages route for all but GNUtls might be good idea - just needs more testing.
That would be sudo apt-get install cmake libglm-dev nettle-dev freeglut3-dev
Then compile GNUtls from source. That worked on my last go around starting with a fresh Ubuntu 14.04 64 bit install.