We are not even getting to the dependancy hell this will involve.
So how do I fix this problem? I'd rather not pave the system and start from scratch, but honestly if I'd done that the moment that this problem manifested, I'd probably be up and running again by now.
This sounds like you have both the i386 package and the x86_64 package installed.
create a .rpmmacros file in root's home directory with the contents -> %_query_all_fmt %%{name}-%%{version}-%%{release}.%%{arch}
then you can run your queries again. This should show that you have: mysql-4.1.20-1.RHEL4.1.i386 mysql-4.1.20-1.RHEL4.1.x86_64
You may also have the same thing for the server. I doubt very much it's a permissions file on the socket, as that's created when the app runs, although improper selinux permissions may cause problems. If the db doesn't contain any data, nuke all the mysql-* packages, and delete the /var/lib/mysql dir. Then install mysql-4.1.20-1.RHEL4.1.x86_64 and mysql-server-4.1.20-RHEL4.1.x86_64