Intente ejecutar 'makewhatis' como root. Eso actualiza la base de datos de la página de manual y la crea si aún no existe, lo que puede no ocurrir en una instalación nueva.
'updatedb' actualiza la base de datos para 'locate' y probablemente no esté relacionado con este problema.
sudo mandb resolvió el problema para mí. Regenera la base de datos apropiada, pero debe asegurarse de ejecutarla con sudo.