Alguma chance de você estar saindo de um disco rígido SSD? Eu tive problemas semelhantes em 12.10 com o meu novo computador. Descobriu-se que era um bug que faz com que o lightdm algumas vezes inicie antes que o driver gráfico da nvidia tivesse tempo de inicializar em sistemas com tempos de carregamento realmente rápidos :) No entanto, parece que foi corrigido em 13.04 (pelo menos para mim)
Minha solução foi editar este arquivo /etc/init/lightdm.conf e antes da linha "exec lightdm" inserir uma nova linha com "sleep 1", então é assim:
sleep 1
exec lightdm
Caso contrário, parece que estamos olhando para um problema de hardware aqui ...