Adicionando 'TERM=xterm' ao alias do meu emacs resolveu o problema:
alias emacs='TERM=xterm; emacs -nw'
Não sei bem por que. Foi inspirado por esta resposta:
Eu recentemente mudei do Ubuntu 15.10 para 16.04. Ao usar o Emacs para editar código Python no Terminal, meu realce de sintaxe parece muito diferente em 16.04 comparado a 15.10 (mais tons de roxo). Isso é verdade, quer eu esteja usando o Emacs localmente ou ssh'ing em outro computador, então parece que tem a ver com o esquema de cores do Terminal e não com o próprio Emacs. Eu não vejo nada no novo arquivo .bashrc ou nas preferências do Terminal que explicaria a diferença, no entanto.
Por padrão, o Terminal usa a paleta de cores do sistema. Você pode mudar isso em Editar > Preferências de perfil > Cores (tab)