When a user is added to Tableau (or really any new item is created; for example, publishing a workbook or data source) the system must index it to make it available for search and retrieval. As such you may notice a slight delay between when the item is created and when it comes back in lists. Typically in our testing this was <2 seconds but that could change based on the total number of users, performance of the system, other activity on the system, and other factors.
As such the behavior you saw is expected. If you're seeing significant delays between adding the user and the user appearing in results it may indicate an overall system performance issue.