I just ran into this exact same issue while trying to update MySQL to 5.5 on a 32-bit installation of CentOS 5.
It seems mysql-libs used to contain that library, but perhaps doesn't anymore? I did a bunch of removing and re-adding packages, and suddenly it just installed mysqlclient16 as a separate package even though it refused to do so before:
Installing for dependencies:
mysqlclient16 i386 5.1.59-1.el5.art atomic 1.8 M
I'm pretty sure what did it was running
rpm -e mysql-libs mysql php-mysql --nodeps
Followed up by installing it again and letting it take care of all dependencies:
yum install mysql
yum install php-mysql
My assumption is that a previous version of mysql-libs did contain mysqlclient16, so whenever it would try to install the mysqlclient16 RPM (which is separate now), it would fail because you already have it installed. Forcing the removal of your mysql-libs package, then installing the latest version would then install the one without mysqlclient16 included, allowing the separate RPM to install without a problem.
Either that or the repo just happened to be updated while I was encountering this issue! (In which case a regular yum update should work fine now).
Hope this helps!