Pelo que entendi, você instalou o metapacote kubuntu-desktop junto com o ubuntu-desktop, de modo que, hoje, você tem Gnome e KDE juntos na mesma máquina. É isto?
Se for o caso, é preciso antes que você preste atenção no seu configurador de login. É recomendável que você tenha instalado o KDM, configurador de login do KDE, para evitar que nestas remoções todas você mande para o buraco o GDM (configurador de login do Gnome) e - com ele - a oportunidade de fazer um login gráfico, um inconveniente grave para o usuário iniciante.
Uma forma radical de remover o gnome seria dar um aptitude --purge libgnome. Como o libgnome é a biblioteca básica do Gnome, todo este ambiente gráfico irá embora com ele. O inconveniente disse idéia seria a remoção de um ou outro aplicativo do Gnome de que você goste.
Caso mude de idéia, basta usar o metapacote ubuntu-desktop (apt-get install ubuntu-desktop) que o Ubuntu voltará inteirinho para você. Mas demora um pouco, é claro.