I would first double check that the @INC variable contains the correct paths and then double check that mysql.pm is not in them with something like:
perl -wE 'for my $d (@INC) { -s "$d/DBD/mysql.pm" and say "$d/DBD/mysq
+l.pm" }'
If it's not present I would go back to the original installation and figure out why they weren't installed. If they are supposed to be there but are not, then something may be wrong with your installation in general.
Also probably worth looking at perl -V | grep version to make sure you are using the perl you think you are using.