Cannot connect to remote postgres database

I have been asked to evaluate Oracle, mysql and postgresql as a possible
replacement for our existing Oracle and MsSQL databases. Oracle and
mysql I pretty much have covered. Postgresql, OTOH, is somewhat less
cooperative.

I have the software (v 8.4.13) installed on 64 bit Centos 6. It is
listening on all available interfaces and netstat confirms this. I
created an additional user for the postgres db:

postgres=# \du
List of roles
Role name | Attributes | Member of
-----------+-------------+-----------
postgres | Superuser | {}
: Create role
: Create DB
stephen | Superuser | {}
: Create role
: Create DB

I assigned passwords using "alter role etc.."

The problem is that no authentication method except trust seems to work.

in pg_hba.conf:

local all all trust
host all all 198.204.114.0/24 md5

I've tried both of the above users and get the same error each time:

psql: FATAL: password authentication failed for user "<username>"

I tried changing "md5" to "password" and "pam" without success. Onlt
"trust" works As near as I can tell by reading the documentation, it is
setup correctly but I have, obviously, done something wrong.

Any hints on where to start looking?

--
Stephen Carville
Apprentice Cook and Bottle Washer
Lereta LLC
1-800-537-3821 X1326