Eu não recomendo que você remova a versão antiga do nautilus, porque ela também removerá o ubuntu-desktop. Enquanto ubuntu-desktop é um pacote meta, e nada vai explodir imediatamente, há uma boa chance de causar problemas de dependência mais tarde.
Em vez disso, sugiro que você atualize para uma versão mais recente do Ubuntu, ou 13.10 ou aguarde alguns meses para o 14.04. Em 13.10 estou usando o Nautilus 3.8.