The first error probably means your libmysqlclient is off someplace where the linker can't find it. Here are some workarounds:

<list>

Find the directory containing libmysqlclient.a and add it to your LD_LIBRARY_PATH env variable

Add said directory to /etc/ld.so.conf and run ldconfig

Recompile the module and statically link it

<list>

As to why the module won't recompile, I'm not sure. Are you using the latest DBD::mysql release? The newer distributions are named DBD-mysql-x.xxxx.tar.gz rather than Msql-Mysql-modules-x.xxxx.tar.gz.

-Matt