Se non l'hai già provato, controlla il tuo file pg_hba.conf. Si chiamerà qualcosa come
/etc/postgresql/9.6/main/pg_hba.conf # Ubuntu 16.04
/var/lib/pgsql/9.3/data/pg_hba.conf # Fedora 20
Potrebbe essere necessario utilizzare find / -name pg_hba.conf per individuarlo.
Nella parte inferiore del file, modifica i valori METHOD in modo che siano attendibili per i test locali (consulta i documenti postgres per informazioni complete). Riavvia postgres per assicurarti che tutto sia avviato pulito e che vengano letti i nuovi parametri:
sudo systemctl restart postgresql # ubuntu
Spero che questo curerà i tuoi guai. Ha risolto i miei problemi su Ubuntu/Fedora.