メーリングリストの皆さま

はじめまして
WEBシステム構築をメインとしている技術者の佐々木浩一と申します。
いつもはJAVA+Oracleを使用しての開発が多いMySQL初心者です。

MySQLは初めてですが、Oracle以外にPostgreSQLなどは環境構築の経験ありです。

今回、依頼元の要望によりシステムの一部をRHEL+MySQL+Perl(CGI)にて
構築する事になり、環境構築を行っているのですが、表題のとおりrootにて
ログイン出来ない状況に陥ってしまいました。過去ログなどを拝見したのですが
ピンと来る情報にたどり着けませんでしたので、ご存知の方がいらっしゃれば
勝手なお願いで恐縮ですが、ご教示頂けませんでしょうか？

【状況】
・依頼元指定のOS(RHEL6.2)のカスタムインストール版OS(MySQLはmysql-libs
 5.1.52-1.el6_0.1のみインストール済)のマシンにMySQL5.6.20-1.el6を
 バンドル版アーカイブファイルからyumでインストール
・MySQLのsharedインストール時、mysql-libs 5.1.52-1.el6_0.1が競合したため、
 代わりにMySQL-shared-compat-5.6.20-1.el6にてmysql-libsのアップデート
・インストールしたパッケージは以下(全て5.6.20-1.el6)
 MySQL-client
 MySQL-devel
 MySQL-server
 MySQL-shared-compat
 MySQL-test
・インストール完了後にOSのrootでMySQLを起動し、起動後に以下のコマンドを実行
 msql -uroot -p
 すると、以下のメッセージが表示された
 Connection using old(pre-4.1.1)authentication protocol refused(client option 'secure_auth' enavled)
・過去ログや他の方のblogなどを拝見した結果、パスワードハッシュの管理に
 変更が入ったこと、およびMySQL5.6から新しい管理方式が標準となったこと
 により発生している問題と理解した
・msql -uroot -pのコマンドに追加パラメータとして--skip-secure-authを追加
 その結果、ログインに成功(rootにパスワードを設定してログアウト)
・mysql起動状態でメモリ使用状況を確認したところ、2Gbyte以上を使用していたため、
 my.cnfに初期メモリなどの設定値を設定しmysqlを再起動
・再度rootでログインしようとしたところ、以下のエラーが発生し再度ログイン出来ず
 Server is running in --secure-auth mode, but 'root@localhost' has a password in the old format; please change the password to the new format
それ以降、何をやっても上記エラーでログイン出来ず

といった状況です。
過去ログや色々な方の記事を拝見すると、そもそも5.1から5.6への更新は推奨されていない
などの断片的な情報は見つかるものの、見つけ出した断片的な情報を試しても解決出来ませんでした。

rootでログイン出来ないとどうする事も出来ず、困っております。

よろしくお願いいたします。