I have installed caffe many times and had it working on ubuntu 14.04 boxes, however it doesn't seem to be working on 16.10, and I have been debugging it quite extensively. I have followed and made changes according to multiple guides but nothing seems to work. It will compile fine if I do not compile it with CUDA, but it will error out if that option is enabled. CUDA is enabled by default but I have to pass it the path so it detects it correctly. Here is a full log which also shows the output of cmake, which shows CUDA 8.0 is detected.
I do cmake this way..
/opt/caffe/build$ sudo cmake -D CUDA_TOOLKIT_ROOT_DIR=/usr/local/cuda-8.0 ..