У меня один раз такая штука возникла. Не стал долго разбираться. Решил перезапустить систему. Если повторится, значит буду думать, а заработает, ну и фиг с ней, с этой ошибкой. Перезапустил машинку. Иконки появились, поиск заработал.
Перед этим, пытался сделать в локальном пользователе файл ~/.local/share/applications/my_app.desktop и как обычно, программа не запускалась. Перед перезапуском системы, всё таки нашел ошибку в своем файле и исправил. Но поиск в линзах к этому времени пропал.