First off, I'm aware I don't have the most recent version of MySQL, but updating that will be a pain and I can deal with it later.

I have these RPM's installed:
php-mysql-4.2.2-17 (not really relevent now that I have php5)
mysql-server-3.23.54a-11 (current server package)
mysql-3.23.54a-11 (current client package)

I successfully installed PHP5 from the source at /usr/local/php-5.0.4

However, it has no mysql support (phpinfo does not list it), and I get a "mysql_connect: function not found" etc etc error.

I tried recompiling with --with-mysql, but it requires a path to the mysql header files, and I have no idea where they are, being that it was installed via RPM.

I can provide any additional information needed. Any help is extremely appreciated.

I had a similar problem quite a while ago. My notes are available here: http://www.gidforums.com/t-842.html.

Though it's not exactly the same setup, the idea is the same, you want to update the MySQL client API. I don't know much about PHP5 (and MySQL 3+) incompatabilities or if any exist...