Zkuste spustit 'makewhatis' jako root. To aktualizuje databázi manuálových stránek a vytvoří ji, pokud již neexistuje, což při nové instalaci nemusí.
'updatedb' aktualizuje databázi na 'locate' a pravděpodobně s tímto problémem nesouvisí.
sudo mandb vyřešil problém za mě. Regeneruje apropos databázi, ale musíte se ujistit, že ji spustíte pomocí sudo.