I am getting the following error when trying to add a user that is not a
member of our domain: "Error, the user does not exist."

I have no problems adding domain users.

Site Settings > Manage Users > Add Users

In step 1, I specify the person's email address.
In step 2, I assign them contributor role
In step 3, enter a username and display name
In step 4, I enter a welcome message

Once I click finish, I get the error message that I noted above.