こんな感じ。 mysqladminとか使う必要なく、直接userテーブルを書き換えれば良い。
[root@localhost ~]# /usr/bin/mysqld_safe --skip-grant-tables &
[1] 3321
[root@localhost ~]# 130319 17:35:28 mysqld_safe Logging to '/var/log/mysqld.log'.
130319 17:35:28 mysqld_safe Starting mysqld daemon with databases from /var/lib/mysql

[root@localhost ~]#
[root@localhost ~]# mysql -uroot
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 2
Server version: 5.1.67 Source distribution

Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> use mysql
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Database changed
mysql> UPDATE user SET Password=PASSWORD('root') WHERE User='root';
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0

mysql> FLUSH PRIVILEGES;
Query OK, 0 rows affected (0.00 sec)

mysql> exit;
Bye
[root@localhost ~]# /sbin/service mysqld stop
130319 17:37:04 mysqld_safe mysqld from pid file /var/run/mysqld/mysqld.pid ended
mysqld を停止中:                                           [  OK  ]
[1]+  終了                  /usr/bin/mysqld_safe --skip-grant-tables
[root@localhost ~]# /sbin/service mysqld start
mysqld を起動中:                                           [  OK  ]
[root@localhost ~]#
[root@localhost ~]# mysql -uroot -p
Enter password:
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 2
Server version: 5.1.67 Source distribution

Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.