Yes. In fact, I would upgrade to the latest stable version of Mysql client (5.something these days). --update: Then, after that's in place, reinstall DBD::mysql, of course.

I'm actually a little surprised that you are running into this problem with a v4.1 mysql server. MySQL changed their (default) password encryption method as of 5.0, and that error message is the one I got whenever I happened to try connecting from a machine with a 4.x client library.