In (at least) the x86_64 RPM set, the library "libmysqlclient.a" is not compiled with -fPIC. This makes it impossible (or maybe just hard) to create a shared object using the library, because the linker complains that "relocation against 'a local symbol' cannot be used".
Frank, seems to me you workaround does not work... maybe if in /usr/lib64 there are some other libmysqlclient.a, compiled correctly, workaround works, but if there is not - no effect.
(for 5.0.16). Do not forget to install gcc-c++ and other devel tools if they are not installed!
After that DBD::mysql installs OK.
It worked fine for all production versions of 5.0.x until 5.0.20.
Now it is not possible to compile anything against libmysqlclient.a  5.0.20(a).
I found a way out to compile Mysql5 and PHP5 on Fedora4 64bits, here is how (hope it helps while we wait for a fix).
First of all remove all Mysql and PHP packages you might have installed.
Now go to your php source folder and run configure to fit your needs (i have php5 compiled with both mysql and mysqli).
PHP5 will now successfully compile (at least mysql wont be a problem anymore).
I had a really bad time getting this to work (and i needed it badly), so i hope this help you guys with similar problems.
I also had to recompile MySQL from src.rpm following Dmitry Koterov's advice above. This way I was able to get new libmysqlclient.a which could be used to compile PHP5 successfully.
I really hope this is fixed soon. It is a major pain to mess with all those different libraries versions.
I was able to rebuild the source-rpm of 5.0.19, so at least I was able to install MySQL. But now I would like to update to version 5.0.21, and it is not possibl to rebuild the source package.
This is a bug, which should be fixed soon, because it is damn uncomfortable to live with these workarounds.
In fact, bug #18091 is a duplicate of this one (or vice versa). I hope, this will be fixed in 5.0.22.