Issue with newly created user: Authenticated successfully, but failed to create new user since creating new users by login is not allowed

We have active directory setup for user authentication in TeamCity. We have a new user with the company that we wish to setup. I went into TeamCity and added a new user that appears to be setup the same as existing users but when the user tries to login, they get the message: "Authenticated successfully, but failed to create new user since creating new users by login is not allowed"

I tried deleting the user from TeamCity and had them login again, as I'd read that with AD, you may not need to create a user first and they can just login, but they got the same error.

How do i resolve this? I don't know how users were setup in the past as the person that did this before is no longer with the company. Maybe I'm doing something wrong in the setup here?