Comment 14 for bug 349607

I believe I know the problem here, and why this has persisted for so long despite apparently "works for me" -- it only occurs on fresh installs, and only before a first apt-get update is run. Similar issues occur with clicking apt-url links -- there's no cache, and so no record of any package in the cache, and so it fails.

To fix this we need to ensure at least one apt-get update is run very early after install time...or during install time.