Usually, to add a user to postgres, you have to run
psql as user
postgres and create user as such.
On Ubuntu it’s enough to let you log in as a newly created user to the DB, but it’s not enough on Fedora. Here psql responds with the error from the subject.
To fix it add the following line to pg_hba.conf (on F23: /var/lib/pgsql/data/pg_hba.conf):
local all all md5
Line above is for socket configuration. If you need IP access too, add:
host all all 127.0.0.1/32 md5