I had the same libmysqlclient problem with RH9.0 MySQL 4.0 and PHP 422.
I solved it by
1. uninstalling the '422 php-msyql' rpm
2. uninstalling the MySQL 4.0 'shared' rpm (and downgrading it by...
3. installing a MySQL 3.23 'shared' rpm
4. re-installed #1.. the 422 php-mysql rpm
Problem Fixed.
In end I now have MySQL 4 rpms (server, client, devel, benchmark) and 1 MySQL 3 'shared rpm
However.. it now works-
Jason