The way that the authentication process works is, if SQL Server doesn't find your user in the contained database you specified, it tries again at the server level, then gives up (it won't go check all the other contained databases in case you match there – I hope you agree that this is a good thing). There is also a new state 65 which occurs if you have specified the correct username and contained database, but entered an incorrect password.
If you connect with a contained user but forget to specify a database name, SQL Server will attempt to authorize you as a SQL login, and you will fail with state 5 (if there is no SQL login with that name) or state 8 (if there is also a SQL login with the same name and the password doesn't match). There are a variety of things that can go wrong here. With this feature comes a new layer of security that may creep onto your radar if you use this functionality: contained user authentication failures. In SQL Server 2012, there is a new feature called "contained databases" – I've blogged about it here and here. I helped our support team just today solve a client's 18456 issues – once we tracked down the error log and saw that it was state 16, it was easy to determine that their login had been set up with a default database that had been detached long ago. In order to figure out what is really going wrong, you need to have alternative access to the SQL Server and inspect the log for the true state in the error message.
In a few cases, some additional information is included, but for the most part several of these conditions appear the same to the end user. The trick to troubleshooting this error number is that the error message returned to the client or application trying to connect is intentionally vague (the error message is similar for most errors, and the state is always 1). I think we've all dealt with error 18456, whether it be an application unable to access SQL Server, credentials changing over time, or a user who can't type a password correctly.
Updated in July 2020 with a few new states