Para alterar o nome de sua máquina (computador) no Linux, você pode seguir ios passos abaixos:

1- Abra uma janela de Terminal
2- Digite o comando abaixo e pressione ENTER

gksudo gedit /etc/hostname

3- Irá surgir um prompt, digite a senha do root e então pressione OK
4- O arquivo hostname será aberto, mostrando o nome atual do computador. Altere para o nome desejado
5- Clique em salvar
7- Faça o mesmo procedimento para o arquivo /etc/hosts
6- Feche todas as janelas e reinicie o sistema.

Após o reinicio, sua máquina já vai estar com o novo nome.

P.S.: A alteração foi feita com o Ubuntu 12.04, mas pode sere feita da mesma forma em qualquer distribuição.