Maybe this is too niche an issue, but in case anyone else runs into this problem, we recently retired one DNS server for another one. A Ubuntu VM I was running didn't pick up on this change. I kept Googling about hosts not resolving in Ubuntu, and people kept pointing to the /etc/hosts and /etc/hostname files. Some older posts from years ago mentioned editing the /etc/resolv.conf file, but the file itself says not to manually edit it! (DO NOT EDIT THIS FILE BY HAND - YOUR CHANGES WILL BE OVERWRITTEN)
Well, turns out that's fine in this case. The wrong address was in there. I hand-edited it to the new address, and now everything's cool.
Looks as if you have to edit the /etc/network/interfaces file to change the dns-nameservers