In addition to the above, it's probably because your perl libs were compiled against a 4.0.x mysql. They changed the way passwords are hashed, so the old client method doesn't work by default wit the server.
If you don't want to recompile your perl libs, then you can change the way your server works by adding a
section of your my.cnf, and then restarting mysql.