Eu não uso o Ubuntu (sou um cara do CentOS / Fedora), mas normalmente isso é feito com runlevels. Estou lendo que, pelo menos no Ubuntu "Gutsy", não há um nível de execução que não inicia o X por padrão. Que dor!
Dê uma olhada no site desse cara - deve pelo menos dar uma ideia de onde procurar. link
Em distribuições no estilo RedHat, isso seria fácil ... > smile <
Eu não sei sobre estas técnicas acima para remover o GDM, mas eu prefiro ser capaz de selecionar um nível de execução diferente para obter X de volta do que remover o software.
Editar: veja alguns pensamentos potencialmente melhores: link