I've used ActiveState Perl 5.8.something with MySql in Win32 without problems, but I worked with an installation of MySQL that came with EasyPHP-1.7, that is MySQL v. 4.0.15.

From the error message about the authentication protocol, I guess that there's been some change in MySQL that probably forces you to recompile your client applications. In this case, I'm talking of the DBD::mysql module, of course: chances are that it's been compiled against an older version of libmysqlclient.whatever that didn't support the new authentication scheme.

On a pragmatical point of view, I'd suggest any of the following:

• On a very lazy ground, try to downgrade your MySQL and see if you've success. If you're happy, you're done :) The laziest solution would be installing EasyPHP 1.7 (beware that the latest release is 1.8).
• Peruse MySQL documentation about this (possibly) new authentication scheme. If I guessed well about it, I also guess that there should be a configuration to set some deprecated way of sticking to the "older" auth scheme, given the fact that 4.1.7 isn't so distant from 4.0.15 IMHO;
• Recompile the DBD::mysql module by your own - here I can't help you, I've used only precompiled modules when I needed them in Win32, but I don't do Win very much.