Есть предложение заменить зависимость от gnome-search-tool на таковую от mate-search-tool -- иначе в менюшке MATE, для которого этот пакет в основном и предназначается, как понимаю, вылазит два пункта "Поиск файлов".
Проверено, отправлено в составе 5.6.5-alt2.