Primeira Maneira: Instalar LightDM
O Ubuntu 12.04 usa o LightDM como gerenciador de exibição padrão. Supondo que o LightDM estava funcionando bem antes de você instalar o GDM, você deve ser capaz de corrigir esse problema certificando-se de que ele está instalado e configurado corretamente.
Pressione Ctrl + Alt + F1 para chegar a um console virtual baseado em texto onde você pode efetuar login sem graficamente. (Ou você pode já estar em tal console.) Então execute estes comandos. (Se o primeiro falhar, os outros ainda podem ter sucesso.)
sudo apt-get update
sudo apt-get install lightdm
sudo dpkg-reconfigure lightdm
Você pode ter a oportunidade de selecionar seu gerenciador de exibição. Se você estiver, selecione LightDM.
Agora reinicie ( sudo reboot / Ctrl + Alt + Del ) ou execute este comando para inicie o LightDM sem reinicializar:
sudo start lightdm
Você deve conseguir fazer login.
Segunda via: instalar o GDM
Se isso não funcionar, mas o GDM funcionou quando foi instalado, basta voltar ao GDM e configurar o sistema para usá-lo. Ou seja, execute as etapas descritas acima, mas para o GDM. Para sua conveniência, depois de ir ao console virtual e efetuar login, estes seriam os comandos:
sudo apt-get remove lightdm
sudo apt-get update
sudo apt-get install gdm
sudo start gdm
Você notará que eu adicionei um comando no início para remover lightdm (porque ele não estava funcionando de qualquer maneira, e removê-lo garante que ele não será executado automaticamente em vez do GDM). Eu também não incluiu um comando dpkg-reconfigure para o GDM. Isso porque você disse que havia removido gdm . Portanto, o comando apt-get install estará fazendo uma nova instalação do pacote, que executará automaticamente qualquer configuração necessária (incluindo a possibilidade de escolher entre gerenciadores de exibição, se houver outro instalado).