Depois de muita dor, descobri que era um problema com meus drivers de placa gráfica. Eu tenho um AMD 8570 HD.
Solução
Livre-se dos drivers proprietários da ATI e instale os de código aberto do Ubuntu. Será necessário eliminar o fglrx * e certificar-se de que instalou tudo de forma limpa. Há muitos guias em sites relacionados ao askubuntu ou ao ubuntu.