Have you installed all the Mysql lib and header packages for your OS?

I always get bit on DBD::mysql until I remember to also install the Mysql-dev packages.

Make sure Mysql is running as well and the makefile knows what your test account is if you took out the stock Mysql "test" accounts and db.

Finally as a last resort, install the DBD tarball by hand (perl Makefile.PL, make, make test, make install) as I have seen that work when the CPAN module got confused.