There really isn't a graceful way to solve this problem that can make everyone 100% happy. If you force the use of email addresses as usernames, you make it easy to determine whether somebody who has a given email address is a user (privacy problem). If you allow arbitrary usernames, you really can't get around eventually revealing whether or not a given username is already in use, and all you can really do is take steps to slow down a user who's trying to discover valid usernames.
New user registrations are the toughest problem to deal with, because there's no getting around the fact that eventually, you're going to have to gracefully deal with a username collision. Here's one possible option: Have the user enter an email address, a proposed username, and the desired password. Upon submit, validate that the password is acceptable, and email the user a validation URL.
If the email address is already in use, but associated with a different username, email that user, remind him that he already has an account, and ask whether he'd like to reset the password.
If the email address isn't already in use, but the username is, email the user an error message letting him know that he needs to pick a different username, and has to wait an increasing amount of time between each attempt.
If the email address and username are both new, email the user a confirmation link that requires re-authenticating with the new username and password before making it official.
DO NOT allow two users to have the same username on the assumption that you can identify one or the other based upon their passwords. Among other things, if two users can share the same username, that means you can never lock out the username due to failed login attempts without affecting BOTH users. And god forbid, if they ever DO happen to somehow pick the same password someday, all hell will break loose.
Don't use the same value for username and public identity. You don't necessarily have to actively prevent users from entering the same value for both if they really WANT to, but the default should be to allow users (on something like a message forum, for instance) to have a public nickname that doesn't necessarily have anything to do with the username they log in with.
Don't sequentially assign user IDs. Use at least 31, preferably 62, bit random values that are generated and verified as unique at registration time. The nice thing about 31 and 62 bit values is the fact that they neatly translate into 6 and 12-character base36 strings. When debugging, it's a lot easier to remember a 6 or 12-character string of lowercase letters and digits than a 6-17 digit decimal value. The hardest part is responding to requests that specify an invalid user ID with responses that are fake, but can't be readily distinguished from real user ID responses by algorithmic means.
Remember: you can not, and will not, ever succeed 100% at stopping an attacker from occasionally verifying whether or not a given user ID or username is valid. Your goal is to make it as slow and expensive as possible, without unreasonably burdening your real users. For a real-world analogue, think about DVD and Blu-Ray region codes. Back when a player cost $500+, region codes were an effective way to stop almost everybody from playing movies purchased from another region. Now that you can buy a Blu-Ray player for $80, and a HDMI selector for $20 and get change back, there's really nothing to stop a film buff from just buying two or three Blu-Ray players (one per desired region), stacking them up, and running them through the HDMI switch.
For routine logins, be purposefully vague about the reason why THIS login attempt failed, but be equally up-front about the possible reasons... and give them concrete contact information of somebody who can assist them. Keep track of failed logins, and lock out the account if too many failed login attempts are made.
Don't tell them outright that the account has just gotten locked out, or is currently locked out... but don't be shy about mentioning it as one of several possible reasons why a login attempt might have failed. Keeping the fact that an account MIGHT be locked out from a user attempting to log in will do nothing to help your security.
You don't necessarily have to lock out an account semi-permanently due to failed login attempts. In many cases, you probably shouldn't, because THEN you'll have created a handy denial of service attack. If an account has too many unsuccessful login attempts, you COULD do a "soft" lockout for 1, 6, or 24 hours, at which point the lock will remove itself. This is the one scenario IMHO where it's legitimate to tell a user to "try again later".
An example error message that might be displayed when a login attempt fails:
The username and/or password you entered was not accepted. You might have entered an invalid username, used an incorrect password, or attempted to log in with an account that has been locked out due to excessive failed login attempts. If the account has been locked out, you can contact ___ for assistance[, or wait _ hours for the account to unlock on its own]. Please note that this error message will be the same for all failed logins, regardless of reason.
DO NOT tell them "Something went wrong, please try again later" unless the problem will literally fix itself on its own. It won't fool an attacker, and will seriously annoy legitimate users. This is one of my ultimate pet peeves, and near the top of my list of "horrible things developers do in the name of security theater". Aside from being incredibly annoying, if somebody's account has been compromised, the LAST thing you want them to do is wait until later before bringing it to somebody's attention.