Acontece que, de alguma forma, os perfis de apparmor para o executável /usr/bin/man
foram corrompidos ou foram sobrescritos com os perfis de uma versão diferente, ou algo assim ... então os avisos permission denied
estavam vindo do apparmor e não das verificações de permissão do sistema de arquivos.
Verificando o syslog mostrou toneladas de mensagens como:
audit: type=1400 audit(1541703091.843:4554): apparmor="DENIED" operation="ptrace" profile="/usr/bin/man" pid=8777 comm="ps" requested_mask="trace" denied_mask="trace" peer="/usr/bin/man"
A solução era uma ferramenta bacana que eu não conhecia chamada aa-logprof , que basicamente analisa os erros do apparmor no seu syslog e (interativamente) pergunta se você deseja ajustar os perfis do apparmor para corrigir as permissões.