What happened to me today: brand new sandbox, impossible to log in after completion of creation. I tried several log in URLs (test, csNN), I tried the log in link from the production org, from the sandbox creation mail, every time: wrong username/password. And I knew the username and password were correct.
Or were they? I re-read the mail I got from Salesforce, about the creation of the sandbox. Turns out: there used to be a sandbox once, with the same name (it didn't exist anymore) and apparently Salesforce remembers the user names it has created. The exact words from the mail: "Some users could not be created with their original user names in this sandbox. This is usually because these users exist in a previously copied sandbox and user names must be unique across all sandboxes."
Salesforce's solution: not only use the familiar suffix, but also a prefix for the usernames ("2tdveaa" in this case, so firstname.lastname@example.org as log in name). Knowing this, I could finally log in.