I was running into a similar issue (on other server though) just after a fresh install and enabling iptables manually (because it didn’t get automatically started after reboot).
Well, even on sudo I was getting this:
sudo: unable to resolve host example.com: Temporary failure in name resolution
Every request was taking ages to response back …
Result is that I needed to allow established connections to continue in iptables:
sudo iptables -A INPUT -m conntrack --ctstate ESTABLISHED,RELATED -j ACCEPT
Why it wasn’t even there at first glance, I have no idea, but my iptables rules didn’t mention that before I added it.