Acontece que o script /etc/init.d/sshd não tinha uma variável $ OPTIONS, que seria a referência ao arquivo de configuração. Portanto, o sshd estava iniciando sem nenhum arquivo de configuração e, portanto, assumindo como padrão "PermitRoodLogin no".
Eu resolvi isso adicionando a seguinte linha perto do início do /etc/init.d/sshd:
OPTIONS="-f /etc/ssh/sshd_config"
Espero que isso ajude alguém.