O problema foi devido à instalação dos drivers Nvidia 3.52 / 3.55 / 3.58 do ppa: graphics-drivers / ppa. Parece que eles podem instalar os drivers, mas ele mexe com algo com o Xorg, fazendo com que ele tenha os erros descritos acima. Quando eu removo qualquer um desses pacotes de driver, o problema desaparece.