Até agora eu tive sucesso fazendo palavrões para emacs e sudo . Edite seu ~/.bashrc (ou ~/.bash_aliases se você usar isso) para incluir o seguinte:
alias emacs="emacs -nw"
alias sudo="sudo "
Ainda estou desapontado que o último emacs-nox não funcione imediatamente.
Atualização: descobri que não removi corretamente a versão antiga do emacs. Certifique-se de quando você executar o comando remove, incluir o * :
apt-get remove emacs*
apt-get install emacs23-nox