I have experienced the same issue today and it took several hours before I have realized that I used to have the same problem with CUDA for Theano. It doesn't have to do with remaking caffe or blas, so don't waste your time on that. The problem is that Caffe won't be able to use CUDA until you launch some CUDA-related program with sudo. I couldn't find the original stackoverflow thread, but I think it said, that you should either launch nvidia-x-server, nvidia-smi or CUDA sample test (deviceQuery) with sudo. I am using the last one and haven't tested the first two this time.
The permanent solution that worked for me was to create a startup file, calling deviceQuery with sudo every time you reboot the system. So I have created a file 'cuda_startup' in /etc/init.d with the following content: 'sudo /usr/local/cuda/samples/1_Utilities/deviceQuery/deviceQuery' and linked it to /etc/rc2.d with terminal command: 'sudo ln -s /etc/init.d/cuda_startup /etc/rc2.d/S99cuda_startup'.