Consegui fazê-lo funcionar após a primeira parte deste link:
$ sudo add-apt-repository ppa:graphics-drivers/ppa
$ sudo apt-get update
$ sudo ubuntu-drivers autoinstall
$ sudo reboot
Later:
> Software & Updates > Additional Drivers
Change from nvidia-364 (open source) to "Using NVIDIA - version 361.42 from nvidia-361 (proprietary)
Um segundo problema que tive com o 16.04 foi que a suspensão / retomada não estava funcionando (por exemplo, Fechar a tampa ou FnF1 no Asus UX303UB). A única maneira que encontrei para consertá-lo e ao mesmo tempo fazer com que os drivers da nvidia funcionassem era usar o Kernel 4.5.4:
$ wget kernel.ubuntu.com/~kernel-ppa/mainline/v4.5.4-yakkety/linux-headers-4.5.4-040504_4.5.4-040504.201605120823_all.deb
$ wget kernel.ubuntu.com/~kernel-ppa/mainline/v4.5.4-yakkety/linux-headers-4.5.4-040504-generic_4.5.4-040504.201605120823_amd64.deb
$ wget kernel.ubuntu.com/~kernel-ppa/mainline/v4.5.4-yakkety/linux-image-4.5.4-040504-generic_4.5.4-040504.201605120823_amd64.deb
$ sudo dpkg -i linux-headers-4.5.4*.deb linux-image-4.5.4*.deb
Tenha cuidado ao usar kernels mais novos (4.6 ..) porque parece que os drivers NVIDIA ainda não compilaram: link
Pelo menos quando eu tentei 4.6, não funcionou no meu notebook. Talvez seja uma boa ideia verificar novamente e isso certamente mudará em breve.