Prova ad eseguire 'makewhatis' come root. Ciò aggiorna il database della pagina man e lo crea se non esiste già, cosa che potrebbe non accadere in una nuova installazione.
'updatedb' aggiorna il database per 'locate' e probabilmente non è correlato a questo problema.
sudo mandb risolto il problema per me. Rigenera il database apropos, ma devi assicurarti di eseguirlo con sudo.