Eu tive exatamente o mesmo problema ao tentar executar o Ubuntu 13.10 com uma placa gráfica AMD / ATI. Eu tentei todos os truques que os usuários úteis do Ubuntu tinham para oferecer, mas nada disso ajudou. Modo gráfico seguro, sem respingos, nodemodeset, somente login no terminal para remover drivers, mas nada ajudou.
O que me deu o erro foi que eu cliquei em "Instalar drivers proprietários de terceiros" quando foi recomendado pelo Ubuntu. Eu reinstalei o Ubuntu e apenas usei os drivers de código aberto, e não tenho problemas agora.
Se você tem "nada a perder" ou apenas fez uma nova instalação, você pode tentar fazer uma reinstalação também e usar drivers de código aberto.