This is because the user credentials are stored in the admin database and not in the default database where the mongo shell connects to (test).
You can change this with the connection URL:
With the admin database:
$ mongo localhost/admin --username user -p
MongoDB shell version: 2.6.9
Enter password:
connecting to: localhost/admin
replset:PRIMARY>
Without a specific database (test by default):
$ mongo localhost --username user -p
MongoDB shell version: 2.6.9
Enter password:
connecting to: localhost
2015-04-22T15:34:28.743+0100 Error: 18 { ok: 0.0, errmsg: "auth failed", code: 18 } at src/mongo/shell/db.js:1260
exception: login failed
With --authenticationDatabase:
$ mongo localhost --username user --authenticationDatabase admin -p
MongoDB shell version: 2.6.9
Enter password:
connecting to: localhost
replset:PRIMARY>
Note that using --host will not assume the database name is the one after the / (slash:
$ mongo --host localhost/admin --username user -p
MongoDB shell version: 2.6.9
Enter password:
connecting to: localhost/admin:27017/test
2015-04-22T15:37:40.703+0100 starting new replica set monitor for replica set localhost with seeds admin:27017
2015-04-22T15:37:40.703+0100 [ReplicaSetMonitorWatcher] starting
2015-04-22T15:37:40.920+0100 getaddrinfo("admin") failed: nodename nor servname provided, or not known
2015-04-22T15:37:40.922+0100 warning: No primary detected for set localhost
2015-04-22T15:37:40.922+0100 All nodes for set localhost are down. This has happened for 1 checks in a row. Polling will stop after 29 more failed checks
2015-04-22T15:37:40.923+0100 Error: connect failed to replica set localhost/admin:27017 at src/mongo/shell/mongo.js:148
exception: connect failed