Adding members to the team returns an error "We can't add a user, They may not have access to teams in your organization." for some sites

Issue Summary

Adding members to the team returns an error "We can't add a user, They may not have access to teams in your organization" for some sites

Steps to Reproduce

1. Create a Team with just yourself as a member
2. After creating the team, try to add members who are not org-admin but have access to at least one product on the site 

Expected Results

Able to add users with access to at least one product on the site

Actual Results

The operation fails with the error:

{
    "members": [],
    "errors": [
        {
            "accountId": "XXXXXXX",
            "code": "ADD_MEMBER_FAILED",
            "message": "We encountered an error trying to add some members to the team. Please check developer documentation."
        }
    ]
} 

Workaround

The org admins can be added without any issues.
Try granting Browse users and group permission to the user who is getting added to the team.This error can also happen due to scenarios discussed here https://support.atlassian.com/atlassian-account/docs/visibility-of-atlassian-teams-information/
However in this case the site is set to with approval. Manually providing product access to a user also results in the same error 
Note: The above steps shared may or maynot work as we see inconsistent behavior for the same configuration.