Unable to remotely connect to Postgresql 9.5 instance

Question

I am struggling to connect to a remote Postgresql 9.5 instance running on Ubuntu 16.10.
The usual:

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

My postgresql.conf includes

listen_addresses='*'

confirmed by output from

netstat -nlp | grep 5432
tcp 0 0 0.0.0.0:5432 0.0.0.0:* LISTEN 22981/postgres 
tcp6 0 0 :::5432 :::* LISTEN 22981/postgres 
unix 2 [ ACC ] STREAM LISTENING 3320886 22981/postgres /var/run/postgresql/.s.PGSQL.5432

Apart from my specific IP address & range, I have also tried the following entries in pg_hba.conf:

host all all 0.0.0.0/0 md5 
host all all ::/0 md5
host all all all md5
host all all * md5 

I have the following ufw rules:

To Action From
-- ------ ----
22/tcp (OpenSSH) ALLOW IN Anywhere 
80,443/tcp (Nginx Full) ALLOW IN Anywhere 
5432 ALLOW IN Anywhere 
22/tcp (OpenSSH (v6)) ALLOW IN Anywhere (v6) 
80,443/tcp (Nginx Full (v6)) ALLOW IN Anywhere (v6) 
5432 (v6) ALLOW IN Anywhere (v6) 

However, the problem persists even when disabling the firewall.

Scanning with nmap:

nmap xx.xx.xx.xx -p5432
Starting Nmap 7.01 ( https://nmap.org ) at 2017年02月13日 09:17 SAST
Nmap scan report for xx.xx.xx.xx
Host is up (0.0074s latency).
PORT STATE SERVICE
5432/tcp filtered postgresql

Almost all similar questions on SE seem to be solved with

listen_addresses='*'

which is not an issue here.

Really confused by this, help would be greatly appreciated.

The machine is not down as I am able to ssh into the machine. Additionally nginx server is also accessible. Telnet to port 5432 times out.

There is no local router in front of the ubuntu server, it is a dedicated server with public network interface that is bound to the xx.xx.xx.xx address. This is a migration from a previous generation box at the same hosting company who does not offer the option of an additional firewall device. This is a clean Ubuntu 16.10 server install.

Answer 1

Turns out my hosting provider moved the server behind a managed firewall without notice.

Answer 2

Though this is already a long ago answered question, for informational purposes to others facing the same issue, in this case the result of nmap does give you the answer as well.

PORT STATE SERVICE --> 5432/tcp filtered postgresql

If you look at the documentation on nmap, it mentions that

Filtered means that a firewall, filter, or other network obstacle is blocking the port so that Nmap cannot tell whether it is open or closed.

So the issue is in the network rather than the PostgreSQL configuration.