Estimado,
Que servidor estas usando ?? Linux, Windows, algun panel de control ??
Te has fijado que la configuración de los Name Servers que estas usando en el server sea correcta ?? Te has fijado en los logs si el servicio es el que falla o si son los name servers ??
Usa
este test, tal vez te de una pista del problema.
Saludos.