Tive o mesmo problema.
sudo apt-get install --reinstall xserver-xorg-core libgl1-mesa-glx
Isso realmente consertou. Ubuntu 13.10 x64 + nVidia 740M. Muito obrigado!
Você não mencionou sua GPU. Se você teve esse problema em um laptop, eu sugiro que seja devido ao chamado sistema "Fusion" (que usa seu GPU integrado em vez de um sistema discreto quando você não precisa dele).