Tente executar o 'makewhatis' como root. Isso atualiza o banco de dados de página de manual e o cria se ele ainda não existir, o que pode não acontecer em uma instalação nova.
'updatedb' atualiza o banco de dados para 'localizar' e provavelmente não está relacionado a esse problema.