Certas classes de cartões NVidia são notoriamente pobres no Linux. Especialmente ao usar os drivers Nouveau de código aberto. Então você precisa dizer qual é a carta.
Eu tenho um 7600GS. Este cartão NUNCA funciona com os drivers NVidia de código aberto, ele fornece os problemas que você mencionou. O truque é alternar para drivers genéricos VESA até que você possa instalar os próprios drivers da NVidia ou inicializar apenas em uma linha de comando, instalar os drivers da NVidia e iniciar o X ou reinicializar.
A página BinaryDriverHowto / Nvidia na documentação do Ubuntu tem mais informações sobre a troca de drivers, incluindo como fazer isso a partir de uma linha de comando usando o comando jockey-text
.