Solution
There are many things that can cause problems with this, however the first step would be to check the exim logs at /var/log/exim_mainlog. This should spell out what the problem is in fairly basic terminology. You will also want to verify that your nameservers in /etc/resolv.conf are set up properly, and pointing to valid IP’s that are answering DNS requests.