If you are in the Admin section of BIM 360 and you are adding a new user to your account, you must create the company they would be assigned to first, then you can create the user and assign them to it.
It would be a much better workflow to be able to just create a new user, then have a company created if one doesn't exist. Maybe even add a checkbox to the user creation dialog that says, create new company for this user, then after you have set the user up, you can go through the process of creating the company in a next step.