Si vous ne l'avez pas déjà essayé, passez en revue votre fichier pg_hba.conf. Il sera nommé quelque chose comme
/etc/postgresql/9.6/main/pg_hba.conf # Ubuntu 16.04
/var/lib/pgsql/9.3/data/pg_hba.conf # Fedora 20
Vous devrez peut-être utiliser find / -name pg_hba.conf pour le localiser.
Au bas du fichier, changez les valeurs METHOD en confiance pour les tests locaux (voir la documentation postgres pour des informations complètes). Redémarrez postgres pour vous assurer que tout est démarré correctement et que les nouveaux paramètres sont lus :
sudo systemctl restart postgresql # ubuntu
Espérons que cela guérira vos malheurs. Cela a résolu mes problèmes sur Ubuntu/Fedora.