Такая же проблема.
PostgreSQL установлен, запущен (systemctl status postgresql выдаёт active).
В pg_hba.conf стоит:
host all all 0.0.0.0/0 md5
host all all ::0/0 md5
В postgres.conf - listen_adresses ="*"
netstat показывает, что порт 5432 открыт:
tcp6 0 0 :::5432 :::* LISTEN 1369/postgres
Подключение по ssh работает и для пользователя postgres, и для вновь созданного пользователя, с паролем. База для нового пользователя одноимённая.
Через pgAdmin подключиться не получается. Ошибка несколько иная, но стабильная: Unable to connect to server. В качестве адреса сервера указываю его IP (это просто VPS).
Что ещё можно придумать, не знаю. Если есть свежие идеи, поделитесь, пожалуйста.