Bem, ele está indo direto para o modo texto correto? Não está aparecendo nenhuma "blue-screen-of-death"?
Se aparecer uma tela dessas para ti, faça o seguinte comando:
sudo dpkg-reconfigure xserver-xorg
Mas atenção, só faça o comando acima se aparecer aquela tela, caso contrário, se o teu "startx" está bom, não faça.
Enfim, para recuperar o Login Gráfico, faça os seguintes comandos no modo texto:
sudo aptitude install gdm
sudo /etc/init.d/gdm restart
É isso.