進展がありましたので一応報告を。
mysqlの起動時に--old-passwordsオプションをつけるなど、色々試したのですがやはり同じエラーで止まってしまいました。
(Apache2+MySQL5.0.27+PHP5.1.6)の環境では何をすればいいか思いつかなかったので、とりあえずPHPのバージョンを下げてみることを試してみました。5.1.6から4.4.4に変更してみたところ、今度は上のエラーは起こらず、インストールを完了することができました。ちなみに、そのときphpinfoでみたMySQLクライアントAPIは5.0.27になっていました。
原因はわかりませんがMySQLとPHPの連携に問題があったようです。
と、無事にmoodle1.6.4+をインストールすることができました。
ただインストールできたとはいえ、crontabの変更でエラーが出る、言語をインポートできないＳＣＯＲＭ教材をアップすることができない（phpのコンフィギュアにzlibオプションをつけなかったため？）など、再びエラー満載の状況に陥っています。明日・明後日で色々と試してみて、もしも行き詰ったらまた新たなトピックで詳細を書き込むこともあるかもしれません。
最後に。Mitsuhiro様、多くの返信ありがとうございました。