Eu resolvi isso. Problema foi que as placas nvidia para notebooks (eu tenho geforce 635M) exigem bumblebee:
sudo add-apt-repository ppa:ubuntu-x-swat/x-updates
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install linux-headers-generic bumblebee bumblebee-nvidia
sudo reboot
Após a reinicialização, rode seus jogos (por exemplo, 0ad) assim:
optirun 0ad
Funciona como charme.