I know this is really old, but I had this same issue and have not seen a fix for it yet.
I am thinking this happened because I decided to turn off my BIND dns server within webmin, I was trying to use digitalocean for all my dns needs instead. I haven’t tested whether this was the cause.
I contacted support and was given two things to do.
The first (did not work for me):
rm -rf /var/lib/apt/lists/*
The second (did work):
change nameserver to 18.104.22.168 and/or 22.214.171.124 in /etc/resolv.conf
Since I am using Virtualmin/ Webmin, I couldn’t just change this file, so I had to do it within webmin. I changed it in two places:
webmin>Networking>Network Configuration>Hostname and DNS Client
These were secondary to 127.0.0.1, so I just removed that one and moved these up on the list.
webmin>Networking>Network Configuration>Host addresses
changed 127.0.0.1 to 126.96.36.199 where it coincides with my web address.