As your ldd output shows, mysql.so (the shared object belonging to DBD::mysql) hasn't been linked against libmysqlclient.so, so no messing with dynamic loader search paths or ldconfig is going to help here, because the loader doesn't even look for the latter library... (it's kind of like fiddling with @INC without having use Module in the code).
Most likely, this is the result of something having gone wrong while building DBD::mysql — presumably the mysql library and/or the header files were not found at build time. So you'll have to rebuild the module, making sure the lib/header files are found this time. See the INSTALL file for how to do a manual installation and specify the respective options to Makefile.PL that tell the build process where to find things.
