There must be a contact with the same email address. You can create the user from the contact data by going to the user's view and clicking the 'create user from contact data' action.
I dont have one with the same email.
What I did for a test is:
1- created a new contact then i click to create a user with it.
2 - I deleted this test user&contact
3- try to recreate a contact with the same parameters
4 - it gives me the same error
any suggestions?