Erro na Hora de Configurar usuário root do Mysql

Estou tentando a muito tempo mudar esta senha do Root e não consigo.

Isso o Sistema CentOs5.4 64 Bits e segui os passos de instalação do site:

http://gnulinuxbr.com/2010/01/19/servidor-mysql-server-no-centos-5-4/

Só que quando chego no passo “8- Após a inicialização do servidor mysql, execute o comando abaixo para poder criar uma senha para o root.

# mysqladmin -u root password ‘senha-do-root-aqui’”

Ele dá um erro e não consigo acessar.

mysqladmin: connect to server at 'localhost' failed
error: 'Access denied for user 'root'@'localhost' (using password: NO)'

Já tentei de tudo, já tentei resetar o Password e nada, já tentei mudar a senha e nada.
Por favor, preciso que vocês me ajudem.

Acesso através do programa Putty e é um servidor externo que contratamos da Uol.
E o melhor que os caras não dão assistência nenhuma.

Desde já agradeço a todos.

1 - Pare o daemon do mysql;
2 - Inicie o MySQL sem que o mesmo leia as as tabelas de permissões
mysqld_safe --skip-grant-tables &
3 - Altere a senha do root
mysqladmin -u root flush-privileges password 'senha'
4 - Finalmente reinicie o daemon.

Após digitar o comando ele deu este erro:

# mysqladmin -u root flush-privileges password 'teste'
mysqladmin: unable to change password; error: 'Can't find any matching row in the user table'

Não contente com o resultado tentei rodar o comando mais uma vez e ele reportou outro erro:

# mysqladmin -u root flush-privileges password 'teste'
mysqladmin: connect to server at 'localhost' failed
error: 'Access denied for user 'root'@'localhost' (using password: NO)'

:(

Na verdade a forma correta é:

mysqladmin -u root password 'senha'
mysqladmin flush-privileges

Ou então conecte-se ao banco:

mysql -u root mysql

E execute essas querys:

UPDATE user SET password = PASSWORD('senha') WHERE user= 'root';
flush privileges;

Mas lembre-se que em ambos os casos, o mysql deverá estar rodando em modo seguro (safe_mysqld –skip-grant-tables &) conforme mostrei acima.