If you are using the wp-invites plugin, it overrides the username check if a user is registering for a blog with an existing username. If the username exists, a new blog will be created under that username, and login details will be emailed to the user who registered using an existing username. However, the login details will not work because the new blog will become associated with the original owner's account. Please check your installation to see if you are having the same issue. In the meantime I will be trying to contact the developer, figure out a fix, or if someone has a fix already, it would be great if you could share.