Altere o /etc/inittab para o runlevel sem X. Varia de distro para distro (não estou em um ubuntu agora para responder com precisão).
O ubuntu server 9.04 utiliza o inittab? acho que não, eu não o instalei, mas o ubuntu não o utiliza desde a versão 7.10 ou 6.alguma coisa.
Mas nunca instalei a versão server, então, criou-se uma pulga atrás de minha orelha.
Caso o ubuntu utilize o upstart, que é o que eu acredito, o comando sudo update-rc.d -f gdm remove tira a interface grafica e o comando sudo update-rc.d -f gdm defaults trás devolta a interface gráfica, sem a necessidade de remover qualquer pacote.
Teste o comando em um sistema a parte e verifique, caso solucione o problema, faça-o no servidor.
Agora, com relação a duvida do companheiro, com o apache e uma gambiarra aqui outra ali, não vejo dificuldade em rodar o webmin, o cups e o swat no mozilla ou internet explorer de qualquer outra maquina, isso permitiria gerenciar impressão, compartilhamentos, permissões e vários outros serviços remotamente em modo gráfico. Mas não tem como fugir do modo texto, se quer administrar um servidor remotamente sem interface gráfica, vai ter que obrigatoriamente acessar o servidor via ssh e trabalhar em modo texto.
robarros, minha opinião é que se você tem dificuldades com comandos, não recomendo fugir de sua dificuldade e trabalhar em modo gráfico, isso não lhe acrescenta nada, esse pensamento é um atraso para quem trabalha com TI, pois somos movidos por desafios. Recomendo que instale o servidor em modo texto e comece a quebrar a cabeça.
Eu particularmente, prefiro quebrar a cabeça, se existe uma ferramenta que eu tenho total domínio e uma nova ferramenta surgindo que desconheço, ao se apresentar um problema com o qual posso resolver com qualquer uma das ferramentas, eu vou utilizar a oportunidade para trabalhar com a nova ferramenta que eu desconheço para solucionar o problema e, algumas vezes, migro tudo que posso para uma nova ferramenta que represente qualquer melhora.