Erro 1045 (28000): Acesso negado para o usuário 'root' @ 'localhost' (usando a senha: YES)

Question

Eu tento definir uma senha de root da seguinte forma:

# mysqladmin -u root password "root";

Então eu faço uma conexão ao meu servidor MySQL, o seguinte comando:

# mysql -u root -p
Enter password: ****

No entanto, recebo o erro abaixo. Como posso resolver isso?