Eu realmente não entendo PORQUE isso aconteceu ... Quero dizer, eu estava usando o servidor sem nenhum problema antes de levá-lo para o novo local e mudar seu IP.
De qualquer forma, eu permiti a porta 80 (que estava executando o Apache) e essa era a solução para o problema.
Vale ressaltar que, mesmo antes de permitir isso, eu tinha (e ainda faço) as portas 22 e 5432 abertas para o PostgreSQL e SSH.
Apenas permitindo que a porta do Apache fizesse o truque.
O que me fez fazer isso foi, quando desativei o firewall, estava tudo bem. Então isso me deu a pista de que o firewall era a causa.
Também vale a pena mencionar que antes de permitir explicitamente a porta 80, quando tentei me conectar ao PGMyAdmin, isso me daria um erro sobre algum problema de SSL. Mas isso foi enganoso (pelo menos para mim).
Espero que outra pessoa ache isso útil.