There are two points, first:
In What is the Directory? How do I use this feature?, part the answer says:
If you have recently tried adding yourself to the Directory, please keep in mind that it is not automatically updated. If you are a new user or have recently changed your settings, it can take between 3 and 12 hours for the updates to take effect. Also, you will not be able to find your listing in the Directory if you have a Free Account, because Free Users do not have access to it.
I do not think this applies now. I have just created an account and edited its info adding a country. Directly afterwards I searched the directory and found them there. I think the only part that still applies is:
Also, you will not be able to find your listing in the Directory if you have a Free Account, because Free Users do not have access to it.
Secondly, there is the issue of the search drop down box. I don't seem to find it anywhere in the FAQ, and I think it's important to mention there. Especially that it allows free users to search.
I've looked at the behavior and noticed that all of the choices are available to free users except for region which uses the directory and is only available to paid users.
I think it'd be a nice idea to have a question like "How do I search for users?" or "How do I find others?" that would contain information about this drop down box, direct users to the directory and mention it's for paid users, and maybe mention http://www.livejournal.com/random.bml for looking for random users. Maybe a few other things I missed too.