O problema era basicamente que os drivers nvidia estragavam o sistema tão mal que a reinstalação da nvidia não funcionava como esperado.
Eles dizem para diagnosticar isso é rodando no terminal: nvidia-smi que retornou.
NVIDIA-SMI falhou porque não conseguiu se comunicar com o driver NVIDIA
A solução foi basicamente uma reinstalação completa do sistema operacional. Então baixando o Ubuntu 16.04 em um drive USB, re-instalar o Ubuntu.
Então:
$ sudo apt-get install linux-headers-$(uname -r)
$ sudo apt-get --purge remove nvidia-*
$ sudo apt autoremove
este é o driver para o GTX 1080 de: link
$ sudo dpkg -i cuda-repo-ubuntu1604_9.1.85-1_amd64.deb
$ sudo apt-key adv --fetch-keys http://developer.download.nvidia.com/compute/cuda/repos/ubuntu1604/x86_64/7fa2af80.pub
$ sudo apt-get update
$ sudo apt-get install cuda
depois reinicie e tudo funciona, por enquanto. Obrigado nvidia pelo seu software inútil!
Aqui está a discussão do tópico de nvidia-forum com alguns detalhes adicionais.