This issue is due to the fact that when a new user is created, Country data is not required and left blank until the user updates his profile information. A Username search does not have a Country filter set, so the user is found by the system.
The First and Last Name searches set the Country filter to United States by default, which causes the the system to ignore the new user because his country location is not set yet.
When going to perform the Search, manually set Country to blank. That will show users in all countries (including no country selected).