Tive o mesmo problema no Ubuntu 16.04 em um vm remoto de openstack recém-criado. sudo su
enforcou por muitos segundos, talvez até um minuto, antes de funcionar ou não. Quando funcionou, pode ser rápido e confiável, executando isso como root:
echo 127.0.0.1 localhost $(hostname) >> /etc/hosts