Desde o Ubuntu 13.10 você deve usar hostnamectl :
sudo hostnamectl set-hostname 'new-hostname'
As vantagens são inúmeras, incluindo um comando para fazer todas essas mudanças, reduzindo problemas com erros de digitação ou sudo (você pode facilmente quebrar o sudo se cometer erros) e não é necessário reiniciar o computador.
Veja também Como eu altero o nome do computador?