DHCPClient não funciona

Tenho um servidor de acesso com dois adaptadores de rede eth0 e eth1. O eth0 está configurado para obter IP via DHCP e estava funcionando sem problemas, sei disso pois fiz vários testes como servidores de DHCP diferentes e tudo correu certinho. Quando coloquei a maquina para rodar (produção) a mesma não recebe o IP designado pelo provedor de acesso (internet). Agora, se coloco a eth1 para se conectar no lugar da eth0 a mesma funciona, ou seja, recebe o IP do DHCP do provedor. O que posso fazer para resolver isso? Já ligue no suporte do provedor e eles falam que lá está tudo certo, que não tem bloqueio algum e muito menos para o MAC da eth0.

Configuração usada:
auto eth0
iface eth0 inet dhcp

Grato e aguardo qualquer ajuda

Ps.: Estou usando o Debian 7 - Wheezy