This has never been a problem for Facebook. People find other people through common friends, not by searching for names.
Also, Facebook doesn't use your name to find your friends, they use your friends list to suggest their friends might be yours as well.
Reason and method are both different.
If anything, real names were far more critical to Facebook's success than they might be to Google+
I find that searching for a specific person through a common friend is a tedious exercise of first going to that common friend's page, locating their friend list and then typing the specific person's first name to filter the list. This is not always fruitful as you would need to know that a specific person is in fact a friend of your suspected common friend, otherwise their profile would not come up in your filtered search.
However, if you type their name in the search input, Facebook will assist you by first finding friends of friends and then people of that name close to your home location.
Friending people as they come up tagged in common friend's activities is not search, it's affinity engagement, which is best achieved when you use your real name or the name most people know you by.