I have spent hours trying to make this work, but its still not working. I tried to connect using my Java program and using pgAdmin III. Postgre is hosted on a Debian 5 64 bit vps and here are the changes I made.
I edited postgresql.conf and changed
listen_addresses = 'local'
to
listen_addresses = '*'
After that I edited pg_hba.conf and added the following line at the end of the file