The most likely cause is a missing role assignment. Both your account and the new user's account need to share at least one common role before you can assign that user as an owner.
After completing these steps, you'll be able to assign the new user as the owner of a data record.
Roles let you build complex hierarchical permission structures. You can read more in the Entitlements and Permissions article.