Modificar senha root do MySQL

Pessoal da lista, boa tarde a todos ....

Acabei de instalar o MySQL , seguindo um tutorial que peguei aqui no Underlinux.
Tem um tópico que diz para modificar a senha de usuário root do MySQL execute :

#/usr/bin/mysqladmin -u root -p 'newpassword'

Quando executo isso aparece :

#Enter new passwd :

Digito uma senha e aparece a seguinte mensagem :

#mysqladmin : connect to server at 'localhost' failed
#error : 'Access denied for user : 'root@localhost' (Using password : YES)'

Sinceramente pessoal. Nunca instalei o MySQL na minha vida. Estou tendo a primeira experiência com o dito cujo.
Alguém poderia me dar alguma dica do que pode ser essa mensagem , por favor ???
Desde já fico gratos a todos ...... :)

Alô galera ....

Desinstalei o mysql e reinstalei novamente. Fiz os procedimentos como está no tutorial aqui do Underlinux.
Fui novamente no item de mudar a senha de root do Mysql assim :

#mysqladmin -u root -h server.localdomain -p password teste

Aparece a resposta assim :

#msqladmin: connect tyo server at 'server.localdomain' failed
#error : 'Access denied for user : '[email protected]' (Using password: YES)

O que pode ser isso galera ???

Quando vc digita /usr/bin/mysqladmin -u root -p password senha .
Ele vai cair na tela pedindo a senha antiga e não a atual , é isso que vc está fazendo ?

Iss
Qual é a senha antiga ??????
Uma vez que estou instalando o MySQL pela primeia vez ........
Eu não sei que senha é essa amigo .........
Se você puder me explicar isso ..............