OK, responderei minha própria pergunta. A cura foi adicionar uma interface externa na linha do iptables, então agora se parece com isso:
ExtIF=eno1 ##Change this to the name of your external (Internet) interface
iptables -t nat -A POSTROUTING -o $ExtIF -j MASQUERADE
Talvez algum guru do iptables seja capaz de responder nos comentários por que a pesquisa de DNS está falhando apenas no localhost, apenas no Ubuntu 18.04.