É uma pergunta complicada, porque a opnião de cada um é bem diferente, mas aqui onde trabalho a migração começou com kde, por ser mais parecido com o windows e facilitar a aceitação do mesmo pelo usuário final. Numa segunda etapa começamos a instalar o gnome para todos (que para mim é mais leve e mais limpo que o kde, e também melhor), e hoje os usuários estão trabalhando com ele sem problemas.
Acho que a escolha depende mesmo do nível dos usuários e de qual ambiente eles se adaptaram melhor, porque em termos de sistema e de atualizações não vejo problemas para nenhuma das duas interfaces.