Occasionally the search index (based on Lucene) can become corrupted. The symptoms of this are that searching for phones or users in different parts of the system will fail to find them.
To rebuild the search index, enter some random text in the search box in the upper right of the Admin GUI and press Enter. A Search page will be displayed and on that page, you'll see a button to 'Rebuild Search Index'. Click on that button and then try your operation again.