Issues with Nvidia graphics driver and CUDA after apt-get upgrade

I had a similar problem. Was able to solve this by installing the recommended version of nvidia driver.

sudo apt-get install ubuntu-drivers-common

sudo ubuntu-drivers devices

sudo apt-get install <recommended version>

A friend was able to solve it for me!

The solution that he showed me was to (after removing all nvidia packages as before)

$ sudo add-apt-repository ppa:graphics-drivers/ppa
$ sudo apt-get install nvidia-364

then download the .run CUDA installer (for me it was cuda_7.5.18_linux.run) from Nvidia and be careful to choose "no" when asked whether you want to install the driver that is packaged with CUDA.