ok, a few things:

ODBC is fine. In some cases, it's the only way to connect to a database engine. DBI is more flexible, but whatever works works.

As others have said, mysql changed the password scheme from 4.0.x->4.1.x. You can either workaround (as others have showed you how) or upgrade your clients or patch old ones (as you tried). I tried to find the clients that you installed at tcx.se, but all I see is a link to www.mysql.com.

Do you know about ppm? ppm is the easiest way to install what you need with windows perl. I do remember having this error some time ago and I used ppm to upgrade the DBD-mysql package. That gives me a \Perl\site\lib\auto\DBD\mysql.dll (no version, 201K, mod time: 8/24/04) that Just Works with 4.1 mysql servers using the new authentication scheme.

I'm sorry that we can't say for sure what went wrong, but it's almost certain that the patches you tried to apply didn't get applied, or else you wouldn't get the error.

--
jpeg