MySql ERROR 1045 (00000): Access denied - different MySQL versions

I need to get an old MySQL Client (4.1) to connect to an even older MySQL Server (3.23).

The goal is to do a Java/JDBC connect to the old Linux/MySQL 3.23 database, in order to update text information for a Lucene search (which will also run on linuxdev2).

The problem is that I can't connect to the Linux/MySQL 3.23 server from a remote Linux/MySql 4.1 client. I can't connect from JDBC; I can't connect from "mysql":

LOCAL (intranet):
mysql -uSOMEUSER -pSOMEPASSWORD mysql => OK

REMOTE (from linuxdev2):
mysql -uSOMEUSER -pSOMEPASSWORD -hintranet mysql => FAILS:
ERROR 1045 (00000): Access denied for user: 'SOMEUSER@linuxdev2' (Using password: YES)

PERMISSIONS (on intranet):
mysql> select User,Host,Password from user order by User;
+-----------+-----------------------------+------------------+
| User      | Host                        | Password         |
+-----------+-----------------------------+------------------+
| SOMEUSER  | %                           | 233780be35015f2c |
| SOMEUSER  | localhost                   | 233780be35015f2c |
| ...

These are the hosts:

Component      Intranet:                Linuxdev2:
---------      --------                 ---------
Java           N/A                      Sun Java 1.5.0_03
JDBC           N/A                      mysql-connector-java-3.1.6-3
MySQl Server   mysql-serve开发者_运维问答r-3.23.22-6   mysql-4.1.10a-3.8
MySql Client   mysql-3.23.22-6          mysql-client-4.1.10a-3

I took an Ethereal trace and verified the TCP/IP connection from linuxdev2 to intranet is OK:

a) They connect on port 3306  
b) Linuxdev2 does a "Login request Caps"
c) Intranet replies with "Response Error Code: 415" (access denied)

MySQL's password algorithm changed in v4.1 - the same password() function, but different hashing algorithms, so connecting with a v4.1+ client to an older v3.x server using password()-created passwords won't work.

Ref: http://dev.mysql.com/doc/refman/5.1/en/password-hashing.html