yum update をかけたら、こんなエラーがでました。

Error: Missing Dependency: mysql-libs = 5.0.54-1.el4.centos is needed by package mysql

でも、rpm を調べるとはいっています。

mysql-libs-5.0.54-1.el4.centos

逆です。「mysql-libs のバージョン:5.0.54-1.el4.centos は、mysql パッケージが必要としています」という意味ですので、インストール済みの mysql-libs を更新しようとしたら、mysql パッケージにとって必須のパッケージだったので、更新に伴うアンインストール処理が出来なかった、という事になります。

同時に mysql パッケージも更新されるのであれば、このような事は通常、起きないので、何らかの原因で、mysql 本体のパッケージが更新対象にならずに、mysql-libs が更新対象になった事が考えられます。

そもそも、

Centos 4 のアップデート用リポジトリ

上記ページを見ると、CentOS 4 に付属する MySQL は Ver 4.1.22 です。CentOS 4 に対して MySQL Ver 5.x のパッケージが入っているみたいですが、CentOS Plus など、デフォルトでは無効になっているリポジトリが有効になっているか、rpmforge や epel などのサードパーティリポジトリや、何らかの形でダウンロードした rpm パッケージでインストールをしていませんか？

yum check-update を実行して見ると、アップデート対象となったパッケージの一覧が表示され、各パッケージがどのリポジトリから取得するのかが表示されるので、mysql-libs がどこのリポジトリから取得されるのかを調べると、原因が分かるかも知れません。

あと、とりあえず、

yum update -x mysql-*

とすれば、mysql に関するパッケージを除いて、他のパッケージを更新する事が出来ます（さらに別の依存関係があって...、という可能性はありますが...）。