Внезапно (сам удивляюсь), а именно после измекнения разрядности цвета в настройках видеокарты (хотя сомневаюсь, что связанно с этим, но это было последнее действие), сглючило Gnome-do - перестал искать, точнее ищет только по точкам входа, а среди программ - нет. Пробовал убивать его настройки (все что нашёл), ключи, переустанавливать - не помогает.