Atualização de 19 de outubro de 2016
Notei que meu módulo Nvidia foi recompilado durante uma atualização hoje, então reiniciei e testei isso novamente. Parece que o problema já foi corrigido. Para referência, estou executando a versão do driver 367.57 em uma Nvidia GTX 970.
Resposta Original
TL; DR
sudo apt-get purge nvidia-* -y
sudo add-apt-repository ppa:graphics-drivers/ppa
sudo apt-get update && sudo apt-get dist-upgrade -y
O ponto crítico aqui é que a instalação dos drivers PPA resulta em
os pacotes libcuda1-361
libxnvctrl0
sendo atualizados, o que resolve o problema. Eu também achei que eu tinha problemas com muitos dos drivers nvidia, então a coisa mais segura a fazer é voltar para o driver opensource. Eu tive algum sucesso com o driver nvidia-340
.
Descrição completa
Ok, de alguma forma eu consegui resolver a situação por acidente
Primeiramente eu instalei o driver ppa:
sudo add-apt-repository ppa:graphics-drivers/ppa
Então eu purgou os drivers nvida existentes
sudo apt-get purge nvidia-*
Então eu instalei os 364 drivers.
sudo apt-get update
sudo apt-get install nvidia-364 -y
Após a reinicialização, não consegui logar no desktop do Ubuntu , mas pude acessar o desktop Xubuntu a partir dos testes anteriores. Isso funcionaria tempo suficiente para eu ver que a reprodução do vídeo funcionava perfeitamente, mas em poucos minutos meu computador travava e precisaria ser reiniciado. Depois de fazer isso algumas vezes eu purgou os drivers nvidia novamente:
sudo apt-get purge nvidia-*
Eu não tenho mais os drivers binários nvidia instalados e estou no driver Nouveau, mas a reprodução de vídeo está funcionando e meu computador não bloqueia!