I made some progress. Basically I looked at the dependencies of the cuda
package in Synaptic and found it depended on nvidia-352
which sounded like it might have the actual driver. So I did the following user-friendly easy command:
sudo apt-get install --reinstall nvidia-352
This gives the following user-friendly error:
ERROR: Cannot create report: [Errno 17] File exists: '/var/crash/nvidia-352.0.crash'
Error! Bad return status for module build on kernel: 4.2.0-35-generic (x86_64)
Consult /var/lib/dkms/nvidia-352/352.79/build/make.log for more information.
Consulting that file and near the end you see this easy-for-beginners-to-understand message:
Compiler version check failed:
The major and minor number of the compiler used to
compile the kernel:
gcc version 5.2.1 20151010 (Ubuntu 5.2.1-22ubuntu2)
does not match the compiler used here:
cc (Ubuntu 4.9.3-5ubuntu1) 4.9.3
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
It is recommended to set the CC environment variable
to the compiler that was used to compile the kernel.
The compiler version check can be disabled by setting
the IGNORE_CC_MISMATCH environment variable to "1".
However, mixing compiler versions between the kernel
and kernel modules can result in subtle bugs that are
difficult to diagnose.
*** Failed CC version check. Bailing out! ***
So what has happened is that CUDA actually only supports GCC 4.9, and apparently the kernel was built with GCC 5.2. I have both installed so I reset the paths to 5.2 using these Windows-shamingly easy-to-use commands:
sudo update-alternatives --config gcc # And choose gcc-5
sudo update-alternatives --config g++ # And choose g++-5
The retry the reinstall. This time it worked. Then I reset my compilers back to 4.9. Going to restart to see it works.
Edit: Yep that works.