ubuntu - Cannot connect to Postgres from remote address

I cannot connect from my machine to a server running Postgres. I think I've configured it all correctly. No firewall are present on the server.

I'm running Postgres 9.1.9 on Ubuntu 12.04 LTS

This is from /etc/postgresql/9.1/main/pg_hba.conf

local   all             postgres                                peer

# TYPE  DATABASE        USER            ADDRESS                 METHOD

local   all             all                                     peer
host    all             all             0.0.0.0/0               md5
host    all             all             ::1/128                 md5

I have listen_addresses = '*' in /etc/postgresql/9.1/main/postgresql.conf

I've stopped and started the service multiple times.

netstat -tulnp:

Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State       PID/Program name
tcp        0      0 0.0.0.0:27017           0.0.0.0:*               LISTEN      19312/mongod    

tcp        0      0 0.0.0.0:28017           0.0.0.0:*               LISTEN      19312/mongod    
tcp        0      0 0.0.0.0:22              0.0.0.0:*               LISTEN      978/sshd        
tcp        0      0 0.0.0.0:5432            0.0.0.0:*               LISTEN      30239/postgres  
tcp6       0      0 :::22                   :::*                    LISTEN      978/sshd        
tcp6       0      0 :::5432                 :::*                    LISTEN      30239/postgres 

My iptable is empty.

When I try to connect to the server with

psql -U postgres -h 

I get:

psql: could not connect to server: Operation timed out
Is the server running on host "" and accepting
TCP/IP connections on port 5432?

Any help? Thanks

tcpdump on port 5432:

16:33:10.548507 7c:c3:a1:a2:d9:27 (oui Unknown) > 00:00:5e:00:01:01 (oui Unknown), ethertype IPv4 (0x0800), length 78:  > .postgresql: Flags [S], seq 95915852, win 65535, options [mss 1460,nop,wscale 4,nop,nop,TS val 1189142453 ecr 0,sackOK,eol], length 0

I can connect to postgres on the server (psql -U postgres -h localhost) but I cannot telnet on 5432 from my machine.