Eu resolvi isso. O problema estava com os drivers da ATI (driver de vídeo do AMD Catalyst ™ 12.10 proprietário Linux x86 que eu tentei). Não é compatível com o xorg 1.13, que está em 12.10. Então há 3 opções
1) Desabilite os Gráficos ATI (do BIOS ou de alguma outra forma no Linux)
2) Instale os drivers legados da ATI
3) Downgrade xorg de 1,13 para 1,12
Eu decidi usar a opção 1, porque quero uma boa aparência no Ubuntu (Gnome 3.6 e suas vantagens).
Mas eu vi que a ATI tem alguns drivers beta nos quais eles estão trabalhando, então espero que o driver funcione.