I finely got it working. In summary for those who are having the same problem.
You will have trouble upgrading by just downloading the mysql rpms and installing them. Redhat currently does not support mysql 4 on RH or Fedora, I have had that problem.
You will have to rebuild new sources for mysql and php. The problem is that you will dependencies errors when trying to install mod_ath_mysql. It will be looking for libmysqlclient.so.10.
So, follow the instructions here to get mysql 4 on RH / FC.
They do work - but be patient - it's time consuming. In summary:
* build mysql from source rpms,
* uninstall mysql 3
* install mysql 4
* uninstall the found dependencies, perl-DBD, mod_auth_mysql, php-mysql.
* build the sources for perl-DBD, php,
* install them,
* install mod_auth_mysql (now it will install correctly since the dependency was related to php-mysql.
You should have a good mysql 4 on RH /FC