É bem simples mudar a senha do Mysql. Siga os seguintes passos:

# /etc/init.d/mysql stop
Stopping MySQL database server: mysqld.

# mysqld_safe –skip-grant-tables &

$ mysql -u root

mysql> use mysql

mysql> update user set password=PASSWORD(“SENHA“) where User=’root’;

mysql> flush privileges;

mysql> quit

# /etc/init.d/mysql restart

Fiz isso para o root, mas você pode fazer para qualquer usuário.

Fonte: http://www.vivaolinux.com.br/dica/ERROR-1045-(28000)-no-MySQL-5-Ubuntu-6.06