お世話になります吉田と申します。
早速ですがMySQL(5.0)へログインできず困っております。

Access denied for user 'root'@'localhost' (using password: YES)

再セットアップもかなら色々とやり直してみましたが駄目でした。

起動オプションで

mysqld_safe --user=mysql --skip-grant-tables

等も試してみましたがどうしても接続できませんでした。

FreeBSDのVPSサーバ（NTT.COM）で、root権限付きのサーバなのですが
vinstallコマンドでMySQLをインストールできるはずなのですが
インストールはできてもrootでのアクセスができません。
mysqlというユーザではアクセスできますが、rootのパスワードを
リセットしようとすると権限エラーが出ます。

何かこのような場合のヒントをいただけませんでしょうか。
お手数をおかけいたしますがどうぞよろしくお願いいたします。