User already exists in your org

We had a user called admin@gochotu.com, I tried to rename it to admins@gochotu.com but I got a message "User already exists in your org".

Then I deleted admin@gochotu.com and tried to create admins@gochotu.com but I still get "User already exists in your org".

Please help.

Thanks,

Bilal Ahmed