Had a bizarre problem with an instance– I cannot install updates or new software. Trying to hit the mirrors always times out. I tried replacing entries in /etc/apt/sources.list with just archive.ubuntu.com addresses but that didn’t work.
The problem turned out to be overly restrictive security groups! At some point, one of the security groups that was supposed to be applied to this instance and allow outbound traffic became unchecked, so requests to the repositories were blocked every time.