E eu notei quantos anos isso tem. Eu tenho que parar de folhear ...: -)
Qualquer que seja o repositório da sua instalação do Ubuntu, o Emacs está provendo a versão x86_64 (bem, isso é o que parece).
Abra o gerenciador de pacotes Synaptic e, no menu "Configurações", selecione "Repositórios".
Verifique se as duas primeiras caixas estão marcadas (main, universe)
Em seguida, mude para o separador "Outro software". Desative temporariamente tudo aqui, mas certifique-se de que não estão marcados.
Clique em Recarregar.
Agora, pesquise o Emacs aqui.
Selecione e instale o emacs.
Isso funcionou? Eu estou realmente supondo aqui. A única vez que vi o mesmo ou quase o mesmo erro foi ao tentar instalar um pacote de 64 bits em uma máquina de 32 bits. Normalmente eu corro apenas estações de trabalho de 64 bits e servidor, então eu não vejo isso com freqüência.