Isto parece que você não instalou realmente o pacote dhcp que você pode verificar com
yum list installed | grep dhcp
verifique se o pacote
dhcp.x86_64 12:4.1.1-31.0.1.P1.el6.centos.1 @updates
ou similar está instalado. Você também deve verificar o seu arquivo /var/log/yum.log
para obter informações relevantes.
Editar: O OP não percebeu que o comando yum install não funcionava. Isso foi causado por arquivos conflitantes de pacotes diferentes. Um
yum update dhclient
consertou o conflito que permitiu progredir.