the authentication error you got would help a lot!

i fired up the postgres image with your arguments:

docker run --name db -d -e POSTGRES_PASSWORD=docker -e POSTGRES_USER=docker postgres

Then I exec'ed in :

docker exec -it db psql -U docker user
psql: FATAL:  database "user" does not exist

I get the error message you are expecting because I have trust authentication :

docker exec -it db cat /var/lib/postgresql/data/pg_hba.conf | grep -v '^#'

local   all             all                                     trust
host    all             all             127.0.0.1/32            trust
host    all             all             ::1/128                 trust
host all all 0.0.0.0/0 md5

To simulate your web container, I'll run another instance of the postgres container and link the db container and then connect back to the db container:

core@ku1 /tmp/i $ docker run --rm --name web --link db:db -it postgres psql -h db -Udocker user
Password for user docker: 
psql: FATAL:  password authentication failed for user "docker"

I get an authentication error if I enter the incorrect password. But, if I enter the correct password:

core@ku1 /tmp/i $ docker run --rm --name web --link db:db -it postgres psql -h db -Udocker user
Password for user docker: 
psql: FATAL:  database "user" does not exist

It all seems to be working correctly. I put it all in a yaml file and tested it that way as well:

web:
  image: postgres
  command: sleep 999
  ports:
    - "62576:62576"
  links:
   - db
db:
  image: postgres
  environment:
    POSTGRES_PASSWORD: docker
    POSTGRES_USER: docker

then fired it up with docker-compose:

core@ku1 /tmp/i $ docker-compose -f dc.yaml up
Creating i_db_1...
Creating i_web_1...
Attaching to i_db_1, i_web_1
db_1  | ok
db_1  | creating template1 database in /var/lib/postgresql/data/base/1 ... ok
db_1  | initializing pg_authid ... ok
db_1  | initializing dependencies ... ok
db_1  | creating system views ... ok
db_1  | loading system objects' descriptions ... ok
db_1  | creating collations ... ok
db_1  | creating conversions ... ok
db_1  | creating dictionaries ... ok
db_1  | setting privileges on built-in objects ... ok
db_1  | creating information schema ... ok
db_1  | loading PL/pgSQL server-side language ... ok
db_1  | vacuuming database template1 ... ok
db_1  | copying template1 to template0 ... ok
db_1  | copying template1 to postgres ... ok
db_1  | syncing data to disk ... ok
db_1  | 
db_1  | WARNING: enabling "trust" authentication for local connections
db_1  | You can change this by editing pg_hba.conf or using the option -A, or
db_1  | --auth-local and --auth-host, the next time you run initdb.
db_1  | 
db_1  | Success. You can now start the database server using:
db_1  | 
db_1  |     postgres -D /var/lib/postgresql/data
db_1  | or
db_1  |     pg_ctl -D /var/lib/postgresql/data -l logfile start
db_1  | 
db_1  | 
db_1  | PostgreSQL stand-alone backend 9.4.1
db_1  | backend> statement: CREATE DATABASE "docker" ;
db_1  | 
db_1  | backend> 
db_1  | 
db_1  | PostgreSQL stand-alone backend 9.4.1
db_1  | backend> statement: CREATE USER "docker" WITH SUPERUSER PASSWORD 'docker' ;
db_1  | 
db_1  | backend> 
db_1  | LOG:  database system was shut down at 2015-04-12 22:01:12 UTC
db_1  | LOG:  database system is ready to accept connections
db_1  | LOG:  autovacuum launcher started
^Z
[1]+  Stopped                 docker-compose -f dc.yaml up
core@ku1 /tmp/i $ bg

you can see that the user and password were created. I exec in:

core@ku1 /tmp/i $ docker exec -it i_web_1 psql -Udocker -h db user
Password for user docker: 
psql: FATAL:  password authentication failed for user "docker"
core@ku1 /tmp/i $
db_1  | FATAL:  password authentication failed for user "docker"
db_1  | DETAIL:  Connection matched pg_hba.conf line 95: "host all all 0.0.0.0/0 md5"

core@ku1 /tmp/i $ docker exec -it i_web_1 psql -Udocker -h db user
Password for user docker: 
psql: FATAL:  database "user" does not exist
db_1  | FATAL:  database "user" does not exist

So the only thing I can think of is that you are trying to connect to the database from your host, not the web container? Or your web container is not using the 'db' as the host to connect to? Your definition for the web container does not contain any errors that I can see.

-g