Eu tive exatamente este mesmo problema após a atualização 16.04.
A coisa é que eu tinha emacs construídos a partir do código-fonte, então resolvi-o: baixando novamente o pacote fonte, compilando & amp; reinstalando.
Consulte o link para obter instruções específicas.
Espero que ajude.