mysql on redhat insanity

I'm trying to get mysql working with DBI on redhat 9, I've put about 10 hours into this so far and I've go no where. I've installed and used mysql with perl many, many times, mostly with debian, but never within the last year or 2.

I tried redhat 9 RPMs and DBD wouldn't install because of a failed dependancy on a library.

I tried yum update of the system and the fedora packages, it all installed and mysqld wouldn't start, complained about incorrect info in hosts.frm. Found some info indicating this was a bug with no fix.

The closest I've come after trying a whole lot of things is mysql 4 RPMs from mysql.com with the latest DBI/DBD built from sources on CPAN. Everything installs and the server works, but I get:

[Mon Dec 13 16:38:23 2004] [error] [client ] cannot connect:
[Mon Dec 13 16:38:23 2004] [error] [client ] DBI
connect('database=;','',...) failed: Client does not support
authentication protocol requested by server; consider upgrading MySQL
client at /(path) line 10

DBD complained about not finding mysql_config but I don't know what to do about that or if it's relevant. I would just wipe the system and go with debian but it would be a big job, so hopefully someone can help get this running without going that route? I swear I'll never use redhat again, I'm ready to throw my monitor through a window, I don't have the patience! Help!