Eu tive esse mesmo problema no Ubuntu 10.10. Foi causado por X (o sistema de janela gráfica) falhando. Qual a placa gráfica que você esta usando? Um bom primeiro passo é verificar se existem drivers proprietários disponíveis para sua placa gráfica. Clique em Configurações do Sistema - > Drivers adicionais.
O que finalmente funcionou para mim foi ativar o repo X-Updates, que tem drivers mais novos, etc.
sudo add-apt-repository ppa:ubuntu-x-swat/x-updates
sudo apt-get update
sudo apt-get upgrade
Reinicie.