client authentication problem

Hi,
I have a problem connecting to a database when using tcp/ip with psql.
Connecting with Unix sockets works fine.  TCP/IP is enabled, and the log
shows a connection is made but authentication is rejected.

 From the error messages, it appears that the client and server negotiated
to use crypt, or perhaps the client is trying to force using crypt rather
than md5.

First guess is something like a version mist-match between client and server
libraries, but this is a fresh install on Debian, installed using apt so
that seems unlikely.  More information follows...

Details:
# uname -a
Linux tova 2.6.8-1-686 #1 Thu Nov 25 04:34:30 UTC 2004 i686 GNU/Linux

# psql -V
psql (PostgreSQL) 7.4.6
contains support for command-line editing

Contents of pg_hba.conf:

local  all  postgres                       ident sameuser
local  all  all                            md5
host   all  all  127.0.0.1 255.255.255.255 md5
host   all  all  0.0.0.0   0.0.0.0         reject


Examining pg_shadow indicates passwords are stored using MD5 encypting.


Connecting directly using Unix sockets works fine:

# psql testdb -U test
<connect ok>

Connecting over TCP/IP fails:

# psql testdb -U test -h localhost
<prompt for password, fail to connect, same with "127.0.0.1" or "localhost">
psql: FATAL:  Password authentication failed for user "test"

The log indicates that a connection was made (so TCP/IP seems to be working
ok) but that the "crypt" authentication method is being used rather than "MD5":

# tail /var/log/postgresql/postgresql.log
LOG:  redo record is at 0/6851324; undo record is at 0/0; shutdown TRUE
LOG:  next transaction ID: 61873; next OID: 28747
LOG:  database system is ready
2005-01-31 16:03:23 [31418] LOG:  connection received: host=127.0.0.1 port=33377
2005-01-31 16:03:23 [31418] LOG:  cannot use authentication method "crypt"
because password is MD5-encrypted
2005-01-31 16:03:23 [31418] FATAL:  Password authentication failed for user
"test"

My understanding of the connection negotiation is that the client connects,
the server suggests the encryption method to use and sends the salt to the
client, the client is supposed to make the MD5 hash using Username, Password
and Salt, and forward that back for authentication.  However it appears that
something is failing at the negotiation stage, and the client is trying to
use crypt, or perhaps the server is suggesting that crypt be used.

Any suggestions on how to correct this problem?

thanks,
   Dave V.