Did you remember to add the new machine to pg_hba.conf?
6.4 is pretty closemouthed about telling you exactly why it's refusing
your connection; "user authentication failed" actually covers a lot of
different reasons. 6.5 will give a bit more info ... hopefully not
enough to risk being a security problem ...
Also, the postmaster log may contain more info than is reported to
the client.
regards, tom lane