No CentOS você faz:
/etc/mail/make
service sendmail restart
Você também precisa ter o pacote sendmail-cf
instalado. Uma simples reinicialização não reconstrói o .cf do .mc.
No entanto (e estou olhando para uma máquina do CentOS 6) o script init chama a rotina updateconf
ao iniciar o sendmail, então lá na 6.x você apenas reinicia. Qual é a saída de
grep make /etc/init.d/sendmail
na sua máquina?
No Debian sendmailconfig
reconstrói o arquivo .cf, se necessário, antes de reiniciá-lo.