Se você ainda não tentou isso, revise seu arquivo pg_hba.conf. Será nomeado algo como
/etc/postgresql/9.6/main/pg_hba.conf # Ubuntu 16.04
/var/lib/pgsql/9.3/data/pg_hba.conf # Fedora 20
Você pode ter que usar find / -name pg_hba.conf para localizá-lo.
Na parte inferior do arquivo, altere os valores de METHOD para trust para testes locais (consulte a documentação do postgres para obter informações completas). Reinicie o postgres para garantir que tudo seja iniciado limpo e que os novos parâmetros sejam lidos:
sudo systemctl restart postgresql # ubuntu
Espero que isso cure seus problemas. Ele resolveu meus problemas no Ubuntu/Fedora.
