Michael said most everything there is to say.
One little obvious thing: Make sure you're logged in. :-)
One totally non-obvious thing: The new search index is updated once a day. If you add someone today, they'll appear in your Watchlist, surname indexes, etc. instantly. But they won't appear in search results until tomorrow morning. This helps us keep the search function zippy.