@Evan:

I believe the important part of the scenario is that the IP is resolving though.  You can see more specifically from the log the time inbetween each attempted file it's trying to fetch:

Apr  7 05:38:33 ubuntu in-target: Err http://archive.canonical.com lucid Release.gpg
Apr  7 05:38:33 ubuntu in-target:   Could not connect to archive.canonical.com:80 (91.189.88.33). - connect (110: Connection timed out)
Apr  7 05:38:54 ubuntu in-target: Ign http://archive.canonical.com lucid Release
Apr  7 05:39:15 ubuntu in-target: Ign http://archive.canonical.com lucid/partner Packages
Apr  7 05:39:36 ubuntu in-target: Ign http://archive.canonical.com lucid/partner Sources
Apr  7 05:39:36 ubuntu in-target: Err http://dz.archive.ubuntu.com lucid Release.gpg
Apr  7 05:39:36 ubuntu in-target:   Could not connect to dz.archive.ubuntu.com:80 (91.189.88.46). - connect (110: Connection timed out) [IP: 91.189.88.46 80]
Apr  7 05:39:57 ubuntu in-target: Ign http://archive.canonical.com lucid/partner Packages
Apr  7 05:40:18 ubuntu in-target: Ign http://archive.canonical.com lucid/partner Sources
Apr  7 05:40:39 ubuntu in-target: Err http://archive.canonical.com lucid/partner Packages
Apr  7 05:40:39 ubuntu in-target:   Could not connect to archive.canonical.com:80 (91.189.88.33). - connect (110: Connection timed out)
Apr  7 05:41:00 ubuntu in-target: Err http://archive.canonical.com lucid/partner Sources
Apr  7 05:41:00 ubuntu in-target:   Could not connect to archive.canonical.com:80 (91.189.88.33). - connect (110: Connection timed out)
Apr  7 05:41:00 ubuntu in-target: Err http://dz.archive.ubuntu.com lucid-updates Release.gpg
Apr  7 05:41:00 ubuntu in-target:   Could not connect to dz.archive.ubuntu.com:80 (91.189.88.46). - connect (110: Connection timed out) [IP: 91.189.88.46 80]
Apr  7 05:42:24 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid Release
Apr  7 05:43:48 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates Release
Apr  7 05:45:12 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/main Packages
Apr  7 05:46:36 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/restricted Packages
Apr  7 05:48:00 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/main Sources
Apr  7 05:49:24 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/restricted Sources
Apr  7 05:50:48 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/universe Packages
Apr  7 05:52:12 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/universe Sources
Apr  7 05:53:36 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/multiverse Packages
Apr  7 05:55:00 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/multiverse Sources
Apr  7 05:56:24 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/main Packages
Apr  7 05:57:48 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/restricted Packages
Apr  7 05:59:12 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/main Sources
Apr  7 06:00:36 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/restricted Sources
Apr  7 06:02:00 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/universe Packages
Apr  7 06:03:24 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/universe Sources
Apr  7 06:04:48 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/multiverse Packages
Apr  7 06:06:12 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/multiverse Sources
Apr  7 06:07:36 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/main Packages
Apr  7 06:09:00 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/restricted Packages
Apr  7 06:10:24 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/main Sources
Apr  7 06:11:48 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/restricted Sources
Apr  7 06:13:12 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/universe Packages
Apr  7 06:14:36 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/universe Sources
Apr  7 06:16:00 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/multiverse Packages
Apr  7 06:17:02 ubuntu CRON[9812]: (root) CMD (   cd / && run-parts --report /etc/cron.hourly)
Apr  7 06:17:24 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid/multiverse Sources
Apr  7 06:18:48 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/main Packages
Apr  7 06:20:12 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/restricted Packages
Apr  7 06:21:36 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/main Sources
Apr  7 06:23:00 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/restricted Sources
Apr  7 06:24:24 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/universe Packages
Apr  7 06:25:01 ubuntu CRON[9852]: (root) CMD (test -x /usr/sbin/anacron || ( cd / && run-parts --report /etc/cron.daily ))
Apr  7 06:25:48 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/universe Sources
Apr  7 06:27:12 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/multiverse Packages
Apr  7 06:28:36 ubuntu in-target: Ign http://dz.archive.ubuntu.com lucid-updates/multiverse Sources
Apr  7 06:30:00 ubuntu in-target: Err http://dz.archive.ubuntu.com lucid/main Packages
Apr  7 06:30:00 ubuntu in-target:   Could not connect to dz.archive.ubuntu.com:80 (91.189.88.46). - connect (110: Connection timed out) [IP: 91.189.88.46 80]
Apr  7 06:31:24 ubuntu in-target: Err http://dz.archive.ubuntu.com lucid/restricted Packages
Apr  7 06:31:24 ubuntu in-target:   Could not connect to dz.archive.ubuntu.com:80 (91.189.88.46). - connect (110: Connection timed out) [IP: 91.189.88.46 80]
Apr  7 06:32:16 ubuntu apt-setup: warning: /usr/lib/ubiquity/apt-setup/generators/91security returned error code 1; discarding output


I can reproduce this consistently, so if you'd like me to throw a set -x somewhere or anything like that followed by fetching debug output, I'd be glad to.