MySQL docs say this. Maybe you're compiling your DBD using an old library? The linked doc suggests a workaround.

For comparison, I have a newer mysqld, an older DBI and DBD::mysql, yet it works for me. I don't know if my admin uses --old-passwords or not.

$ mysql -u ... -p
Enter password:
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 723796 to server version: 4.0.18
...
$ perl -MDBI -le'print($DBI::VERSION)'
1.40
$ perl -MDBD::mysql -le'print($DBD::mysql::VERSION)'
2.0419
[download]