Unable to add particular users as a member to public channel

Do those users have access to the team where the channel is located?
Are you using Bleve or Elasticsearch? This could be related to this report Not all persons inside a channel are shown anymore - if you have details on the questions shared by our staff, this can help us diagnose the issue further (Not all persons inside a channel are shown anymore - #7 by jesse & Not all persons inside a channel are shown anymore - #8 by agnivade).