Quoting Jim Perrin jperrin@gmail.com:
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.
For mysql package, that is perfectly OK. mysql.i386 has 32-bit libs, mysql.x86_64 has 64-bit libs.
/var/lib/mysql isn't part of mysql package. It's part of mysql-server package. Therefore, uninstalling mysql package isn't likely to fix anything. However, if David still wants to do it, the right option to use is --allmatches (as documented in rpm man page).
Now, before doing anything drastic. David, do you have SELinux running on the box? If so, is there anything logged in /var/log/messages when you attempt to start MySQL? Also, it'd be interesting to see output of "ls -lZd / /var /var/lib /var/lib/mysql".