Hey Phil, the Jenkins Userdatabase is just a folder in your JENKINS_HOME Directory. "Users" is where you find all your "Members". Maybe, just remove the folder from one of your users, who is getting the Error Message, "Username is already taken". Now he should be able to register again.
I also tried to "delete a user" in the Jenkins "User Page". After "You really want to delete..." the user was not shown on the User Page. So, just check, if there is a Folder at the JENKINS_HOME users Directory.
