Temporary failure in name resolution
Solution 1:
This might be a problem caused by DHCP server -actually, by a rogue or another misconfigured DHCP server on your network.
Probably, this is what happens: when your server boots, it manages to get the accurate parameters (IP address, gateway, DNS servers, etc) from the legit DHCP server and as a result, you won't experience any problems until the lease renewal. After a relatively short period of time (it depends on dhcp client and server configuration), the DHCP client will attempt to renew the lease, by contacting the legit DHCP server (via unicast transmission). If this for some reason fails or your dhcp client for some reason doesn't get a response from the legit DHCP server, it will get into rebinding state and will broadcast a request to extend the lease time. If the rogue/another misconfigured DHCP server manages to respond first, it might send to your DHCP client inacurate parameters -for example a "wrong" DNS server address, and as a result you won't be able to resolve hostnames.
If my speculation is right, rebooting your server does not always solve the problem, since there might be times when the rogue DHCP server responds first, and as a result you experience the problem you mentioned.
In any case, try configuring static IP addresses, disabling DHCP and setting manually DNS servers. Also you should probably check if any other DHCP servers are running on your network, besides the one you're using.
Solution 2:
In my case, I'd set the fw rules up for the wrong interface. So port 53 wasn't open, and the server couldn't make a dns req