O comando correto no seu caso será echo "newhostname" | sudo tee /etc/hostname , porque, como nssnd explicou, sudo aplica-se apenas ao comando único e o redirecionamento tem menos prioridade que sudo . Outra opção é usar o comando bash :
sudo bash -c "echo newhostname > /etc/hostname"