If you have not tried this already, review your pg_hba.conf file. It will be named something like /var/lib/pgsql/9.3/data/pg_hba.conf (Fedora 20); you may have to use 'find / -name pg_hba.conf' to locate it.
At the bottom of the file, change the 'METHOD' values to 'trust' for local testing (see postgres docs for full information). Reboot the machine to ensure everything is started clean and the new params are read.
Hopefully this will cure your woes. It solved my problems on Fedora 20 with PostgreSQL 9.3.
UPDATE 2016-10-14:
On Ubuntu, the needed filename is /etc/postgresql/9.5/main/pg_hba.conf
. For local testing only, modify it to look like this:
...
#
# Database administrative login by Unix domain socket
local all postgres peer
# TYPE DATABASE USER ADDRESS METHOD
# "local" is for Unix domain socket connections only
# local all all peer
local all all trust
# IPv4 local connections:
# host all all 127.0.0.1/32 md5
host all all 127.0.0.1/32 trust
The two lines with METHOD "trust" are new. They allow you to connect without a username/password.
When complete, you will need to restart the server via:
sudo systemctl restart postgresql