Угодай n/a пишет:
> иногда простейший apt-cache search выполняется десятки минут.
> Процессор не используется, и память тоже. Процесс просто висит и
> ничего не делает. Воспроизвести условия, когда apt так себя ведёт не
> получается. Что делать?
>   
Может ждет пока завершится другой процесс?
Посмотрите, в этот момент rpm или apt не висит?

-- 
С уважением,
Дубровский Вячеслав.