I'm kind of brainstorming some ideas, but the goal is to keep it simple and minimal. Focus on doing well at locating people's contact info.
here are some thoughts
with just search box i don't see any contacts at first visit, add some clue that i will get people's profile using search (don't do that with that one paragraph of text). you can list people's name with profile link in place of the text you are showing below search box (manage this text somewhere with Help??? link). you can work on yammer or LinkedIn like email verification. don't list contacts unless they are from verified domains. make browsing contacts more visible - allow peoples to tag their info and allow browsing by tags too. don't show actual email in plain text on public listing. and when i update settings, info is getting replicated check that too.
good luck. John Doe