With every new release of Mac OS X, the need to
re-install Perl's MySQL driver "DBD::mysql" arises again. And every single time it does not work out of the box (i.e. using cpan). Since I'm giving up using Perl and write my new scripts (yes, also the Shell scripts) in PHP, partially because of problems like this, I was able to postpone dealing with this problem, which arised after installing Snow Leopard - up until today.
If you have the problem it is most likely (and has always been) due to wrong paths to MySQL's header files. The fix is simple, and if you google for it people were complaining about the same problem even under OS X 10.2. Here's the solution: Build the thing manually, giving the right paths to Makefile.PL:
$ perl Makefile.PL \
--cflags="-I/usr/local/mysql/include -Os -arch x86_64 -arch i386 -fno-common" \
--libs="-L/usr/local/mysql/lib -lmysqlclient -lz -lm"
Rafael: Thank you very much, I was having a huge headache to solve the very same problem!