Deixe-me ser rápido e conciso sem dizer palavrões
O problema foi a Nvidia, eu tenho uma pista de este tópico
Reinstalado com alguns problemas, ele reclamou de uma versão incompatível do gcc (4.6 vs 4.8).
Eu tentei empurrar o 4.8 para cima, embora parecesse que era assim, mas sem sucesso ...
Então eu removi completamente qualquer traço de 4.6, ainda problemas
Então eu removi todos os gcc e recuperei o 4.8 reinstalando o build-essential, que também cuidava de algumas configurações, como eu esperava
Rebooted, funcionou