Some of our existing agents can't see newly created agents to assign a ticket only for some tickets? Why?

Please check if the ticket already has a group selected in it and if they are trying to assign an agent when the ticket is already in the group. Try removing the group and searching for the Newly added agents. You can add the new agents in the groups by navigating to Admin--> Groups.