A user with this nickname already exists.

I have tried to replicate this myself, but have thus far been unable to.  A client contacted me with a problem they were having when trying to create a new user.  They were seeing " A user with this nickname already exists."  

Apparently the client had created the user account and forgot to assign the roles to the user that were required.  For whatever reason instead of just editing the user account they chose to delete them and re-create it.  It was at this point the error triggered.

The user account was in fact removed and there is no one else using the even remotely similar information with another username.  I also verified this by checking the sf_users table which came up empty for any of the information on the user.  What is odd is that the sf_sitefinity_profile table had an orphaned record for this user which is what was causing the error on the nickname field.  I removed this record and was able to then create the user.

I tested this two ways so far:
1.) I entered the information the client was trying to use.  I cannot post that here for obvious reasons, but username, password, email, First name, Last name and Nickname were filled in and then "This user can access site backend " was not selected.  No other roles were selected.

I saw the same error the client was seeing.

2.) I then  created a new account with test information.
username: stestuser
password: *****
confirm:*****
email: stestuser@test.com
First name: Test
Last name: User
Nickname: stestuser

This user can access site backend = unchecked
No other roles were selected.

Next I removed this test account and then tried to enter it again with the same exact information.  No errors and the account went in.

My best guess right now is something timed out or a connection conflict interrupted the delete process before it could clean up the profile information.

I am having the same problem. 
Simply - I create a new user and save. 
The user doesn't show up in the list, however only if you click on the role they are in, do they show up.
If you click to edit them, it always says the "A user with this nickname already exists.
I needed to add the user's First and Last name because for some reason it didn't save. So instead I logged in as the user and tried to do it in the edit Profile.  It also gave me the same error.
It looks like there is some disconnect between the tables (sf_users, sf_user_profile,  sf_sitefinity_profile?)
The  table sf_sitefinity_profile has the first name and last name filled in but is doesn't show up anywhere in the backend. (user listing, user profile, etc)

We are using verison 5.1 Claims Based Authentication  and I find it to be problematic.