Update-Manager fails - bug 346836

sudo apt-get --yes --quiet --allow-unauthenticated install medibuntu-keyring && sudo apt-get --quiet update

Should install the key you need to authenticate the medibuntu ppa

steven@steven-desktop:~$ sudo apt-get --yes --quiet --allow-unauthenticated install medibuntu-keyring
Reading package lists...
Building dependency tree...
Reading state information...
E: Unable to locate package medibuntu-keyring
steven@steven-desktop:~$

Try the following commands from a terminal

sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 2EBC26B60C5A2783
sudo apt-get update

and then copy/paste all output into a new message of this question thread

steven@steven-desktop:~$ sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 2EBC26B60C5A2783
[sudo] password for steven:
Executing: gpg --ignore-time-conflict --no-options --no-default-keyring --secret-keyring /etc/apt/secring.gpg --trustdb-name /etc/apt/trustdb.gpg --keyring /etc/apt/trusted.gpg --primary-keyring /etc/apt/trusted.gpg --keyserver keyserver.ubuntu.com --recv-keys 2EBC26B60C5A2783
gpg: requesting key 0C5A2783 from hkp server keyserver.ubuntu.com
gpg: key 0C5A2783: public key "Medibuntu Packaging Team <email address hidden>" imported
gpg: no ultimately trusted keys found
gpg: Total number processed: 1
gpg: imported: 1
steven@steven-desktop:~$ sudo apt-get update
Ign http://dl.google.com stable InRelease
Get:1 http://dl.google.com stable Release.gpg [198 B]
Get:2 http://dl.google.com stable Release [1,338 B]
Get:3 http://extras.ubuntu.com natty InRelease [308 B]
Ign http://extras.ubuntu.com natty InRelease
Get:4 http://security.ubuntu.com natty-security InRelease [320 B]
Ign http://security.ubuntu.com natty-security InRelease
Get:5 http://dl.google.com stable/main i386 Packages [464 B]
Get:6 http://archive.canonical.com natty InRelease [312 B]
Get:7 http://archive.ubuntu.com natty InRelease [310 B]
Ign http://archive.ubuntu.com natty-updates InRelease
Ign http://archive.canonical.com natty InRelease
Ign http://archive.ubuntu.com natty InRelease
Ign http://dl.google.com stable/main TranslationIndex
Ign http://archive.ubuntu.com natty-updates Release.gpg
Get:8 http://extras.ubuntu.com natty/main TranslationIndex [314 B]
Get:9 http://packages.medibuntu.org natty InRelease [7,092 B]
Get:10 http://archive.ubuntu.com natty/universe i386 Packages/DiffIndex [341 B]
Ign http://archive.ubuntu.com natty/main i386 Packages/DiffIndex
Ign http://archive.ubuntu.com natty/restricted i386 Packages/DiffIndex
Ign http://archive.ubuntu.com natty/multiverse i386 Packages/DiffIndex
Ign http://archive.ubuntu.com natty/main TranslationIndex
Ign http://archive.ubuntu.com natty/multiverse TranslationIndex
Ign http://archive.ubuntu.com natty/restricted TranslationIndex
Ign http://archive.ubuntu.com natty/universe TranslationIndex
Get:11 http://archive.canonical.com natty/partner i386 Packages/DiffIndex [342 B]
Hit http://packages.medibuntu.org natty/free Sources
Hit http://archive.ubuntu.com natty-updates Release
Hit http://archive.ubuntu.com natty/universe i386 Packages
Hit http://archive.ubuntu.com natty/main i386 Packages
Hit http://archive.ubuntu.com natty/restricted i386 Packages
Hit http://archive.ubuntu.com natty/multiverse i386 Packages
Get:12 http://archive.ubuntu.com natty/main Translation-en_US [332 B]
91% [12 Translation-en_US bzip2 0 B] [Waiting for headers] [Waiting for headersbzip2: (stdin) is not a bzip2 file.
Ign http://archive.canonical.com natty/partner TranslationIndex
Hit http://packages.medibuntu.org natty/non-free Sources
Get:13 http://archive.canonical.com natty/partner i386 Packages [337 B]
91% [13 Packages bzip2 0 B] [Waiting for headers] [Waiting for headers] [Waitinbzip2: (stdin) is not a bzip2 file.
Get:14 http://security.ubuntu.com natty-security/main i386 Packages/DiffIndex [347 B]
Ign http://security.ubuntu.com natty-security/restricted i386 Packages/DiffIndex
Ign http://security.ubuntu.com natty-security/multiverse i386 Packages/DiffIndex
Ign http://security.ubuntu.com natty-security/main TranslationIndex
Ign http://security.ubuntu.com natty-security/multiverse TranslationIndex
Ign http://security.ubuntu.com natty-security/restricted TranslationIndex
Hit http://packages.medibuntu.org natty/free i386 Packages
Ign http://archive.ubuntu.com natty-updates/main i386 Packages/DiffIndex
Ign http://archive.ubuntu.com natty-updates/restricted i386 Packages/DiffIndex
Ign http://archive.ubuntu.com natty-updates/multiverse i386 Packages/DiffIndex
Ign http://archive.ubuntu.com natty-updates/main TranslationIndex
Ign http://archive.ubuntu.com natty-updates/multiverse TranslationIndex
Ign http://archive.ubuntu.com natty-updates/restricted TranslationIndex
Ign http://archive.ubuntu.com natty-updates/universe TranslationIndex
Ign http://security.ubuntu.com natty-security/universe TranslationIndex
Hit http://security.ubuntu.com natty-security/restricted i386 Packages
Hit http://security.ubuntu.com natty-security/multiverse i386 Packages
Get:15 http://security.ubuntu.com natty-security/main Translation-en_US [342 B]
89% [15 Translation-en_US bzip2 2 B] [Waiting for headers] [Waiting for headersbzip2: (stdin) is not a bzip2 file.
Get:16 http://archive.ubuntu.com natty/multiverse Translation-en [334 B]
89% [16 Translation-en xz 0 B] [Waiting for headers] [Waiting for headers] [Wai/usr/bin/xz: (stdin): File format not recognized
Get:17 http://extras.ubuntu.com natty/main Translation-en_US [331 B]
Hit http://archive.ubuntu.com natty-updates/restricted i386 Packages
89% [17 Translation-en_US lzma 2 B] [Waiting for headers] [Waiting for headers]/usr/bin/lzma: Decoder error
Hit http://packages.medibuntu.org natty/non-free i386 Packages
Hit http://archive.ubuntu.com natty-updates/multiverse i386 Packages
Get:18 http://archive.ubuntu.com natty-updates/main Translation-en_US [340 B]
89% [18 Translation-en_US bzip2 0 B] [Waiting for headers] [Waiting for headersbzip2: (stdin) is not a bzip2 file.
Err http://extras.ubuntu.com natty/main i386 Packages
  0 Ok
Get:19 http://archive.canonical.com natty/partner Sources [338 B]
Ign http://packages.medibuntu.org natty/free TranslationIndex
Get:20 http://security.ubuntu.com natty-security/multiverse Translation-en_US [349 B]
90% [20 Translation-en_US lzma 0 B] [Waiting for headers] [Waiting for headers]/usr/bin/lzma: Decoder error
Ign http://extras.ubuntu.com natty/main Translation-en_US
Ign http://packages.medibuntu.org natty/non-free TranslationIndex
Ign http://extras.ubuntu.com natty/main Translation-en
Err http://security.ubuntu.com natty-security/universe i386 Packages
  0 Ok [IP: 91.189.92.167 80]
Get:21 http://security.ubuntu.com natty-security/main Translation-en [338 B]
Get:22 http://archive.ubuntu.com natty-updates/restricted Translation-en [344 B]
Ign http://archive.ubuntu.com natty/main Translation-en
88% [22 Translation-en lzma 2 B] [Waiting for headers] [Waiting for headers] [W/usr/bin/lzma: Decoder error
Ign http://archive.ubuntu.com natty/main Translation-en_US
Ign http://archive.ubuntu.com natty/multiverse Translation-en_US
Ign http://archive.ubuntu.com natty/restricted Translation-en_US
Ign http://archive.ubuntu.com natty/multiverse Translation-en
Ign http://archive.ubuntu.com natty/restricted Translation-en
Ign http://archive.ubuntu.com natty/universe Translation-en_US
Err http://security.ubuntu.com natty-security/main i386 Packages
  0 Ok [IP: 91.189.92.167 80]
Ign http://dl.google.com stable/main Translation-en_US
Ign http://archive.ubuntu.com natty/universe Translation-en
Err http://archive.ubuntu.com natty-updates/universe i386 Packages
  0 Ok [IP: 91.189.88.31 80]
Ign http://security.ubuntu.com natty-security/main Translation-en_US
Ign http://security.ubuntu.com natty-security/multiverse Translation-en
Ign http://security.ubuntu.com natty-security/restricted Translation-en_US
Ign http://security.ubuntu.com natty-security/restricted Translation-en
Ign http://security.ubuntu.com natty-security/multiverse Translation-en_US
Ign http://dl.google.com stable/main Translation-en
Ign http://security.ubuntu.com natty-security/universe Translation-en_US
Ign http://security.ubuntu.com natty-security/universe Translation-en
Get:23 http://archive.ubuntu.com natty-updates/multiverse Translation-en [342 B]
Err http://archive.ubuntu.com natty-updates/main i386 Packages
  404 Not Found [IP: 91.189.88.31 80]
Ign http://archive.ubuntu.com natty-updates/main Translation-en
Get:24 http://archive.ubuntu.com natty-updates/multiverse Translation-en_US [342 B]
Ign http://archive.ubuntu.com natty-updates/restricted Translation-en_US
Ign http://archive.ubuntu.com natty-updates/universe Translation-en_US
Ign http://archive.ubuntu.com natty-updates/universe Translation-en
Ign http://archive.ubuntu.com natty-updates/restricted Translation-en
Ign http://packages.medibuntu.org natty/free Translation-en_US
Ign http://packages.medibuntu.org natty/free Translation-en
Ign http://packages.medibuntu.org natty/non-free Translation-en_US
Ign http://packages.medibuntu.org natty/non-free Translation-en
Get:25 http://archive.canonical.com natty/partner Translation-en_US [333 B]
Ign http://archive.canonical.com natty/partner Translation-en
Fetched 8,997 B in 18s (479 B/s)
W: GPG error: http://extras.ubuntu.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://security.ubuntu.com natty-security InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://archive.canonical.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://archive.ubuntu.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: Failed to fetch http://extras.ubuntu.com/ubuntu/dists/natty/main/binary-i386/Packages 0 Ok

W: Failed to fetch http://security.ubuntu.com/ubuntu/dists/natty-security/universe/binary-i386/Packages 0 Ok [IP: 91.189.92.167 80]

W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/natty-updates/universe/binary-i386/Packages 0 Ok [IP: 91.189.88.31 80]

W: Failed to fetch http://security.ubuntu.com/ubuntu/dists/natty-security/main/binary-i386/Packages 0 Ok [IP: 91.189.92.167 80]

W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/natty-updates/main/binary-i386/Packages 404 Not Found [IP: 91.189.88.31 80]

E: Some index files failed to download. They have been ignored, or old ones used instead.
steven@steven-desktop:~$

Try the following:

open update-manager and change to a mirror server near your location (instead of archive.ubuntu.com) and close update-manager

The issue the following terminal commands:

sudo rm -rf /var/lib/apt/lists
sudo mkdir /var/lib/apt/lists
sudo mkdir /var/lib/apt/lists/partial
sudo apt-get update

and copy/paste all output into this answer thread as done before

If I understand the question correctly, I just solved the same problem with the help of this post: http://kubuntuforums.net/forums/index.php?topic=3117133.msg264930#msg264930

This was my situation:
The update manager showed that "the package information was last updated 73 days ago".

stefanie@BlackCheetah:~$ sudo apt-get update
[...]
Err http://packages.medibuntu.org natty InRelease
[...]
Reading package lists... Done
W: A error occurred during the signature verification. The repository is not updated and the previous index files will be used. GPG error: http://packages.medibuntu.org natty InRelease: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 2EBC26B60C5A2783
W: Failed to fetch http://packages.medibuntu.org/dists/natty/InRelease
W: Some index files failed to download. They have been ignored, or old ones used instead.
stefanie@BlackCheetah:~$

stefanie@BlackCheetah:~$ sudo apt-get install medibuntu-keyring
Reading package lists... Done
Building dependency tree
Reading state information... Done
medibuntu-keyring is already the newest version.
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
stefanie@BlackCheetah:~$

Here is what I did:
stefanie@BlackCheetah:~$ sudo apt-key adv --recv-keys --keyserver keyserver.ubuntu.com 2EBC26B60C5A2783
Executing: gpg --ignore-time-conflict --no-options --no-default-keyring --secret-keyring /etc/apt/secring.gpg --trustdb-name /etc/apt/trustdb.gpg --keyring /etc/apt/trusted.gpg --primary-keyring /etc/apt/trusted.gpg --recv-keys --keyserver keyserver.ubuntu.com 2EBC26B60C5A2783
gpg: requesting key 0C5A2783 from hkp server keyserver.ubuntu.com
gpg: key 0C5A2783: public key "Medibuntu Packaging Team <email address hidden>" imported
gpg: no ultimately trusted keys found
gpg: Total number processed: 1
gpg: imported: 1
stefanie@BlackCheetah:~$

stefanie@BlackCheetah:~$ sudo apt-get update
Ign http://archive.canonical.com natty InRelease
[...]
Ign http://de.archive.ubuntu.com natty-proposed/universe Translation-en
Reading package lists... Done
stefanie@BlackCheetah:~$

Now the update manager says: "The package information was last updated less than one hour ago."

steven@steven-desktop:~$ sudo rm -rf /var/lib/apt/lists
[sudo] password for steven:
steven@steven-desktop:~$ sudo mkdir /var/lib/apt/lists
steven@steven-desktop:~$ sudo mkdir /var/lib/apt/lists/partial
steven@steven-desktop:~$ sudo apt-get update
Ign http://dl.google.com stable InRelease
Get:1 http://archive.canonical.com natty InRelease [312 B]
Ign http://archive.canonical.com natty InRelease
Get:2 http://dl.google.com stable Release.gpg [198 B]
Get:3 http://packages.medibuntu.org natty InRelease [7,092 B]
Get:4 http://us.archive.ubuntu.com natty InRelease [313 B]
Ign http://us.archive.ubuntu.com natty-updates InRelease
Ign http://us.archive.ubuntu.com natty InRelease
Get:5 http://security.ubuntu.com natty-security InRelease [320 B]
Ign http://security.ubuntu.com natty-security InRelease
Get:6 http://extras.ubuntu.com natty InRelease [308 B]
Ign http://extras.ubuntu.com natty InRelease
Get:7 http://dl.google.com stable Release [1,338 B]
Ign http://us.archive.ubuntu.com natty-updates Release.gpg
Get:8 http://dl.google.com stable/main i386 Packages [464 B]
Get:9 http://archive.canonical.com natty/partner i386 Packages [7,861 B]
Get:10 http://us.archive.ubuntu.com natty/universe i386 Packages [6,021 kB]
Get:11 http://extras.ubuntu.com natty/main TranslationIndex [314 B]
Ign http://archive.canonical.com natty/partner TranslationIndex
Get:12 http://packages.medibuntu.org natty/free Sources [3,293 B]
Get:13 http://security.ubuntu.com natty-security/main i386 Packages [153 kB]
Get:14 http://archive.canonical.com natty/partner Sources [328 B]
0% [14 Sources xz 0 B] [10 Packages 18.6 kB/6,021 kB 0%] [Waiting for headers] /usr/bin/xz: (stdin): File format not recognized
Get:15 http://packages.medibuntu.org natty/non-free Sources [4,361 B]
Get:16 http://security.ubuntu.com natty-security/restricted i386 Packages [14 B]
Get:17 http://security.ubuntu.com natty-security/multiverse i386 Packages [2,074 B]
Get:18 http://packages.medibuntu.org natty/free i386 Packages [3,262 B]
Ign http://security.ubuntu.com natty-security/main TranslationIndex
Ign http://security.ubuntu.com natty-security/multiverse TranslationIndex
Ign http://security.ubuntu.com natty-security/restricted TranslationIndex
Ign http://security.ubuntu.com natty-security/universe TranslationIndex
Get:19 http://security.ubuntu.com natty-security/universe i386 Packages [343 B]
6% [19 Packages xz 0 B] [10 Packages 189 kB/6,021 kB 3%] [Waiting for headers] /usr/bin/xz: (stdin): File format not recognized
Get:20 http://extras.ubuntu.com natty/main Translation-en_US [331 B]
7% [20 Translation-en_US lzma 0 B] [10 Packages 286 kB/6,021 kB 4%] [Waiting fo/usr/bin/lzma: Decoder error
Get:21 http://packages.medibuntu.org natty/non-free i386 Packages [6,689 B]
Get:22 http://archive.canonical.com natty/partner Translation-en_US [338 B]
8% [22 Translation-en_US lzma 0 B] [10 Packages 309 kB/6,021 kB 5%] [Waiting fo/usr/bin/lzma: Decoder error
Err http://extras.ubuntu.com natty/main i386 Packages
  0 Ok
Err http://archive.canonical.com natty/partner Sources
  0 Ok
Ign http://dl.google.com stable/main TranslationIndex
Ign http://packages.medibuntu.org natty/free TranslationIndex
Get:23 http://archive.canonical.com natty/partner Translation-en [333 B]
Get:24 http://security.ubuntu.com natty-security/main Translation-en_US [343 B]
11% [24 Translation-en_US lzma 0 B] [10 Packages 543 kB/6,021 kB 9%] [Waiting f/usr/bin/lzma: Decoder error
Ign http://extras.ubuntu.com natty/main Translation-en_US
Ign http://archive.canonical.com natty/partner Translation-en_US
Ign http://packages.medibuntu.org natty/non-free TranslationIndex
Ign http://extras.ubuntu.com natty/main Translation-en
Err http://security.ubuntu.com natty-security/universe i386 Packages
  0 Ok [IP: 91.189.92.167 80]
Ign http://security.ubuntu.com natty-security/main Translation-en
Ign http://security.ubuntu.com natty-security/multiverse Translation-en_US
Ign http://security.ubuntu.com natty-security/multiverse Translation-en
Ign http://security.ubuntu.com natty-security/main Translation-en_US
Ign http://security.ubuntu.com natty-security/restricted Translation-en_US
Ign http://security.ubuntu.com natty-security/restricted Translation-en
Ign http://security.ubuntu.com natty-security/universe Translation-en_US
Ign http://security.ubuntu.com natty-security/universe Translation-en
Ign http://dl.google.com stable/main Translation-en_US
Ign http://dl.google.com stable/main Translation-en
Ign http://packages.medibuntu.org natty/free Translation-en_US
Ign http://packages.medibuntu.org natty/free Translation-en
Ign http://packages.medibuntu.org natty/non-free Translation-en_US
Ign http://packages.medibuntu.org natty/non-free Translation-en
Get:25 http://us.archive.ubuntu.com natty/main i386 Packages [1,550 kB]
Get:26 http://us.archive.ubuntu.com natty/restricted i386 Packages [8,986 B]
Get:27 http://us.archive.ubuntu.com natty/multiverse i386 Packages [183 kB]
Ign http://us.archive.ubuntu.com natty/main TranslationIndex
Ign http://us.archive.ubuntu.com natty/multiverse TranslationIndex
Ign http://us.archive.ubuntu.com natty/restricted TranslationIndex
Ign http://us.archive.ubuntu.com natty/universe TranslationIndex
Get:28 http://us.archive.ubuntu.com natty-updates Release [27.2 kB]
Get:29 http://us.archive.ubuntu.com natty/main Translation-en_US [335 B]
99% [29 Translation-en_US bzip2 0 B] [Waiting for headers] 398 kB/s 0sbzip2: (stdin) is not a bzip2 file.
Get:30 http://us.archive.ubuntu.com natty-updates/main i386 Packages [275 kB]
Get:31 http://us.archive.ubuntu.com natty-updates/restricted i386 Packages [14 B]
Get:32 http://us.archive.ubuntu.com natty-updates/multiverse i386 Packages [4,267 B]
Ign http://us.archive.ubuntu.com natty-updates/main TranslationIndex
Ign http://us.archive.ubuntu.com natty-updates/multiverse TranslationIndex
Ign http://us.archive.ubuntu.com natty-updates/restricted TranslationIndex
Ign http://us.archive.ubuntu.com natty-updates/universe TranslationIndex
Get:33 http://us.archive.ubuntu.com natty/multiverse Translation-en [337 B]
99% [33 Translation-en xz 0 B] [Waiting for headers] 398 kB/s 0s/usr/bin/xz: (stdin): File format not recognized
Get:34 http://us.archive.ubuntu.com natty-updates/restricted Translation-en [347 B]
Ign http://us.archive.ubuntu.com natty/main Translation-en
99% [34 Translation-en lzma 0 B] [Waiting for headers] 398 kB/s 0s/usr/bin/lzma: Decoder error
Ign http://us.archive.ubuntu.com natty/main Translation-en_US
Ign http://us.archive.ubuntu.com natty/multiverse Translation-en_US
Ign http://us.archive.ubuntu.com natty/multiverse Translation-en
Ign http://us.archive.ubuntu.com natty/restricted Translation-en_US
Ign http://us.archive.ubuntu.com natty/restricted Translation-en
Ign http://us.archive.ubuntu.com natty/universe Translation-en_US
Ign http://us.archive.ubuntu.com natty/universe Translation-en
Err http://us.archive.ubuntu.com natty-updates/universe i386 Packages
  0 Ok [IP: 91.189.88.40 80]
Ign http://us.archive.ubuntu.com natty-updates/main Translation-en_US
Ign http://us.archive.ubuntu.com natty-updates/main Translation-en
Ign http://us.archive.ubuntu.com natty-updates/multiverse Translation-en_US
Ign http://us.archive.ubuntu.com natty-updates/multiverse Translation-en
Ign http://us.archive.ubuntu.com natty-updates/restricted Translation-en_US
Get:35 http://us.archive.ubuntu.com natty-updates/universe Translation-en_US [343 B]
Ign http://us.archive.ubuntu.com natty-updates/universe Translation-en
Ign http://us.archive.ubuntu.com natty-updates/restricted Translation-en
Fetched 8,264 kB in 24s (343 kB/s)
W: GPG error: http://archive.canonical.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://us.archive.ubuntu.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://security.ubuntu.com natty-security InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://extras.ubuntu.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: Failed to fetch http://archive.canonical.com/ubuntu/dists/natty/partner/source/Sources 0 Ok

W: Failed to fetch http://security.ubuntu.com/ubuntu/dists/natty-security/universe/binary-i386/Packages 0 Ok [IP: 91.189.92.167 80]

W: Failed to fetch http://extras.ubuntu.com/ubuntu/dists/natty/main/binary-i386/Packages 0 Ok

W: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/natty-updates/universe/binary-i386/Packages 0 Ok [IP: 91.189.88.40 80]

E: Some index files failed to download. They have been ignored, or old ones used instead.
steven@steven-desktop:~$

What happens if you issue the command

sudo apt-get update

again? Do identical error messages pop up, or do they differ?

Here's the command I tried next:

steven@steven-desktop:~$ sudo apt-get upgrade
Reading package lists... Error!
E: Encountered a section with no Package: header
E: Problem with MergeList /var/lib/apt/lists/archive.canonical.com_ubuntu_dists_natty_partner_i18n_Translation-en
E: The package lists or status file could not be parsed or opened.
steven@steven-desktop:~$

The solution for this one is straightforward:

sudo rm /var/lib/apt/lists/archive.canonical.com_ubuntu_dists_natty_partner_i18n_Translation-en

and then try again

sudo apt-get update

steven@steven-desktop:~$ sudo rm /var/lib/apt/lists/archive.canonical.com_ubuntu_dists_natty_partner_i18n_Translation-en
[sudo] password for steven:
steven@steven-desktop:~$ sudo apt-get update
Ign http://dl.google.com stable InRelease
Get:1 http://dl.google.com stable Release.gpg [198 B]
Get:2 http://dl.google.com stable Release [1,338 B]
Get:3 http://archive.canonical.com natty InRelease [312 B]
Get:4 http://us.archive.ubuntu.com natty InRelease [313 B]
Ign http://us.archive.ubuntu.com natty-updates InRelease
Get:5 http://security.ubuntu.com natty-security InRelease [320 B]
Hit http://packages.medibuntu.org natty InRelease
Ign http://archive.canonical.com natty InRelease
Ign http://us.archive.ubuntu.com natty InRelease
Get:6 http://extras.ubuntu.com natty InRelease [308 B]
Ign http://security.ubuntu.com natty-security InRelease
Ign http://extras.ubuntu.com natty InRelease
Get:7 http://dl.google.com stable/main i386 Packages [464 B]
Ign http://us.archive.ubuntu.com natty-updates Release.gpg
Ign http://dl.google.com stable/main TranslationIndex
Get:8 http://us.archive.ubuntu.com natty/universe i386 Packages/DiffIndex [344 B]
Ign http://us.archive.ubuntu.com natty/main i386 Packages/DiffIndex
Ign http://us.archive.ubuntu.com natty/restricted i386 Packages/DiffIndex
Ign http://us.archive.ubuntu.com natty/multiverse i386 Packages/DiffIndex
Ign http://us.archive.ubuntu.com natty/main TranslationIndex
Ign http://us.archive.ubuntu.com natty/multiverse TranslationIndex
Ign http://us.archive.ubuntu.com natty/restricted TranslationIndex
Ign http://us.archive.ubuntu.com natty/universe TranslationIndex
Get:9 http://archive.canonical.com natty/partner i386 Packages/DiffIndex [342 B]
Get:10 http://extras.ubuntu.com natty/main TranslationIndex [314 B]
Ign http://security.ubuntu.com natty-security/main i386 Packages/DiffIndex
Ign http://security.ubuntu.com natty-security/restricted i386 Packages/DiffIndex
Ign http://security.ubuntu.com natty-security/multiverse i386 Packages/DiffIndex
Ign http://security.ubuntu.com natty-security/main TranslationIndex
Ign http://security.ubuntu.com natty-security/multiverse TranslationIndex
Ign http://security.ubuntu.com natty-security/restricted TranslationIndex
Ign http://security.ubuntu.com natty-security/universe TranslationIndex
Hit http://packages.medibuntu.org natty/free Sources
Ign http://archive.canonical.com natty/partner TranslationIndex
Get:11 http://us.archive.ubuntu.com natty-updates Release [27.2 kB]
Get:12 http://security.ubuntu.com natty-security/universe i386 Packages [343 B]
42% [12 Packages xz 0 B] [11 Release 9,832 B/27.2 kB 36%] [Waiting for headers]/usr/bin/xz: (stdin): File format not recognized
Hit http://us.archive.ubuntu.com natty/universe i386 Packages
Hit http://us.archive.ubuntu.com natty/main i386 Packages
Hit http://us.archive.ubuntu.com natty/restricted i386 Packages
Hit http://us.archive.ubuntu.com natty/multiverse i386 Packages
Hit http://packages.medibuntu.org natty/non-free Sources
Get:13 http://archive.canonical.com natty/partner i386 Packages [337 B]
96% [13 Packages bzip2 0 B] [Waiting for headers] [Waiting for headers] [Waitinbzip2: (stdin) is not a bzip2 file.
Get:14 http://us.archive.ubuntu.com natty/restricted Translation-en [338 B]
96% [14 Translation-en bzip2 0 B] [Waiting for headers] [Waiting for headers] [bzip2: (stdin) is not a bzip2 file.
Hit http://packages.medibuntu.org natty/free i386 Packages
Ign http://us.archive.ubuntu.com natty-updates/main i386 Packages/DiffIndex
Ign http://us.archive.ubuntu.com natty-updates/restricted i386 Packages/DiffIndex
Ign http://us.archive.ubuntu.com natty-updates/multiverse i386 Packages/DiffIndex
Ign http://us.archive.ubuntu.com natty-updates/main TranslationIndex
Ign http://us.archive.ubuntu.com natty-updates/multiverse TranslationIndex
Ign http://us.archive.ubuntu.com natty-updates/restricted TranslationIndex
Ign http://us.archive.ubuntu.com natty-updates/universe TranslationIndex
Get:15 http://security.ubuntu.com natty-security/restricted i386 Packages [14 B]
Get:16 http://security.ubuntu.com natty-security/multiverse i386 Packages [2,074 B]
Get:17 http://us.archive.ubuntu.com natty/multiverse Translation-en [337 B]
97% [17 Translation-en xz 0 B] [Waiting for headers] [Waiting for headers] [Wai/usr/bin/xz: (stdin): File format not recognized
Get:18 http://security.ubuntu.com natty-security/main i386 Packages [339 B]
97% [18 Packages xz 0 B] [Waiting for headers] [Waiting for headers] [Waiting f/usr/bin/xz: (stdin): File format not recognized
Ign http://dl.google.com stable/main Translation-en_US
Get:19 http://extras.ubuntu.com natty/main Translation-en_US [331 B]
Hit http://packages.medibuntu.org natty/non-free i386 Packages
97% [19 Translation-en_US lzma 2 B] [Waiting for headers] [Waiting for headers]/usr/bin/lzma: Decoder error
Ign http://dl.google.com stable/main Translation-en
Get:20 http://archive.canonical.com natty/partner Sources [338 B]
Get:21 http://security.ubuntu.com natty-security/main Translation-en_US [343 B]
97% [21 Translation-en_US lzma 2 B] [Waiting for headers] [Waiting for headers]/usr/bin/lzma: Decoder error
Err http://extras.ubuntu.com natty/main i386 Packages
  0 Ok
Err http://security.ubuntu.com natty-security/universe i386 Packages
  0 Ok [IP: 91.189.92.166 80]
Ign http://packages.medibuntu.org natty/free TranslationIndex
Get:22 http://us.archive.ubuntu.com natty-updates/restricted i386 Packages [14 B]
Get:23 http://us.archive.ubuntu.com natty-updates/multiverse i386 Packages [4,267 B]
Ign http://packages.medibuntu.org natty/non-free TranslationIndex
Ign http://extras.ubuntu.com natty/main Translation-en_US
Get:24 http://us.archive.ubuntu.com natty/main Translation-en_US [336 B]
96% [24 Translation-en_US lzma 0 B] [Waiting for headers] [Waiting for headers]/usr/bin/lzma: Decoder error
Ign http://extras.ubuntu.com natty/main Translation-en
Ign http://security.ubuntu.com natty-security/main Translation-en
Ign http://security.ubuntu.com natty-security/multiverse Translation-en_US
Ign http://security.ubuntu.com natty-security/main Translation-en_US
Ign http://security.ubuntu.com natty-security/multiverse Translation-en
Ign http://security.ubuntu.com natty-security/restricted Translation-en_US
Ign http://security.ubuntu.com natty-security/restricted Translation-en
Ign http://security.ubuntu.com natty-security/universe Translation-en_US
Ign http://security.ubuntu.com natty-security/universe Translation-en
Get:25 http://us.archive.ubuntu.com natty-updates/restricted Translation-en [347 B]
Ign http://us.archive.ubuntu.com natty/main Translation-en_US
95% [25 Translation-en lzma 2 B] [Waiting for headers] [Waiting for headers] [W/usr/bin/lzma: Decoder error
Ign http://us.archive.ubuntu.com natty/main Translation-en
Ign http://us.archive.ubuntu.com natty/multiverse Translation-en_US
Ign http://us.archive.ubuntu.com natty/restricted Translation-en_US
Ign http://us.archive.ubuntu.com natty/multiverse Translation-en
Ign http://us.archive.ubuntu.com natty/universe Translation-en_US
Ign http://us.archive.ubuntu.com natty/restricted Translation-en
Ign http://us.archive.ubuntu.com natty/universe Translation-en
Err http://us.archive.ubuntu.com natty-updates/universe i386 Packages
  0 Ok [IP: 91.189.92.171 80]
Get:26 http://us.archive.ubuntu.com natty-updates/multiverse Translation-en [345 B]
Err http://us.archive.ubuntu.com natty-updates/main i386 Packages
  404 Not Found [IP: 91.189.92.171 80]
Ign http://us.archive.ubuntu.com natty-updates/main Translation-en_US
Ign http://us.archive.ubuntu.com natty-updates/main Translation-en
Get:27 http://us.archive.ubuntu.com natty-updates/multiverse Translation-en_US [345 B]
Ign http://us.archive.ubuntu.com natty-updates/restricted Translation-en_US
Ign http://us.archive.ubuntu.com natty-updates/universe Translation-en_US
Ign http://us.archive.ubuntu.com natty-updates/universe Translation-en
Ign http://us.archive.ubuntu.com natty-updates/restricted Translation-en
Ign http://packages.medibuntu.org natty/free Translation-en_US
Ign http://packages.medibuntu.org natty/free Translation-en
Ign http://packages.medibuntu.org natty/non-free Translation-en_US
Ign http://packages.medibuntu.org natty/non-free Translation-en
Get:28 http://archive.canonical.com natty/partner Translation-en_US [333 B]
Ign http://archive.canonical.com natty/partner Translation-en
Fetched 42.3 kB in 18s (2,260 B/s)
W: GPG error: http://archive.canonical.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://us.archive.ubuntu.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://security.ubuntu.com natty-security InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: GPG error: http://extras.ubuntu.com natty InRelease: The following signatures were invalid: NODATA 1 NODATA 2
W: Failed to fetch http://security.ubuntu.com/ubuntu/dists/natty-security/universe/binary-i386/Packages 0 Ok [IP: 91.189.92.166 80]

W: Failed to fetch http://extras.ubuntu.com/ubuntu/dists/natty/main/binary-i386/Packages 0 Ok

W: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/natty-updates/universe/binary-i386/Packages 0 Ok [IP: 91.189.92.171 80]

W: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/natty-updates/main/binary-i386/Packages 404 Not Found [IP: 91.189.92.171 80]

E: Some index files failed to download. They have been ignored, or old ones used instead.
steven@steven-desktop:~$
steven@steven-desktop:~$ sudo apt-get upgrade
Reading package lists... Error!
E: Encountered a section with no Package: header
E: Problem with MergeList /var/lib/apt/lists/archive.canonical.com_ubuntu_dists_natty_partner_binary-i386_Packages
E: The package lists or status file could not be parsed or opened.
steven@steven-desktop:~$

As it can be seen from the previous messages you are fully hit by bug 346836. 'apt-get update' creates files with wrong contents (not containing the Package: header as it should be). It is not clear to me why this happens. One situation that has been reported is the following: The internet connection does not work the standard way and delivers just the data, but comes up with something like a 'proxy authorization page' first. apt cannot handle such situation well. Do you know about any peculiarity of your internet connection that might be responsible for the wrong data?

If you issue "cat /var/lib/apt/lists/archive.canonical.com_ubuntu_dists_natty_partner_binary-i386_Packages" what are the contents of that file?

If you try to reach the following servers with your web browser:
http://archive.canonical.com
http://dl.google.com
http://extras.ubuntu.com
http://packages.medibuntu.org
http://security.ubuntu.com
http://us.archive.ubuntu.com
Do you see any problem or error message?

You definitely should try to upgrade to the modified apt version (0.8.13.2ubuntu4.1), which contains extra logic to partly cover that situation. The only problem is that you cannot do the automatic upgrade because of exactly that error.

I recommend to try the following:
issue the command "sudo apt-get upgrade"
if there is an error message shown "... E: Problem with MergeList ..." note down the name of the file that is shown in the message. issue "sudo rm <filename from error message>"
issue "sudo apt-get update"
Repeat these steps until no "E:" or "Err" message is shown any more (or until you realize that you are running in a loop).

Hopefully "sudo apt-get upgrade" will then be able to upgrade apt.

steven@steven-desktop:~$ cat /var/lib/apt/lists/archive.canonical.com_ubuntu_dists_natty_partner_binary-i386_Packages
<SCRIPT language=JavaScript>
var job = location.host + location.pathname;
var job = job.replace(/ /g, '+');
window.location = 'http://websearch.linksys.com/?eg=' + '1254433856' + '&job=' + job;
</SCRIPT>
                                                                                                                                steven@steven-desktop:~$

All of the sites listed I can reach except http://security.ubuntu.com - it redirects to http://www.ubuntu.com/usn/ and gives message 503 Service Unavailable.

I'll try your recommendation and see what happens.

That seemed to work and got me most of the way there. After several packages updated/upgraded, I seem to be stuck at this point:

steven@steven-desktop:~$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages have been kept back:
  linux-generic linux-headers-generic linux-image-generic
0 upgraded, 0 newly installed, 0 to remove and 3 not upgraded.
steven@steven-desktop:~$

When I try to run Update Manager, it gives error "Requires installation of untrusted packages" and won't continue.

sudo apt-key adv --recv-key --keyserver keyserver.ubuntu.com 2EBC26B60C5A2783

steven@steven-desktop:~$ sudo apt-key adv --recv-key --keyserver keyserver.ubuntu.com 2EBC26B60C5A2783
Executing: gpg --ignore-time-conflict --no-options --no-default-keyring --secret-keyring /etc/apt/secring.gpg --trustdb-name /etc/apt/trustdb.gpg --keyring /etc/apt/trusted.gpg --primary-keyring /etc/apt/trusted.gpg --recv-key --keyserver keyserver.ubuntu.com 2EBC26B60C5A2783
gpg: requesting key 0C5A2783 from hkp server keyserver.ubuntu.com
gpg: key 0C5A2783: "Medibuntu Packaging Team <email address hidden>" not changed
gpg: Total number processed: 1
gpg: unchanged: 1
steven@steven-desktop:~$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages have been kept back:
  linux-generic linux-headers-generic linux-image-generic
0 upgraded, 0 newly installed, 0 to remove and 3 not upgraded.
steven@steven-desktop:~$

try
sudo apt-get dist-upgrade

That seemed to work, and all of the command-line stuff seems to be working now.

But when I try to use Update Manager, it throws this error - Failed to download repository information - Check your internet connection. Details:

W:GPG error: http://us.archive.ubuntu.com natty InRelease: File /var/lib/apt/lists/partial/us.archive.ubuntu.com_ubuntu_dists_natty_InRelease doesn't start with a clearsigned message, W:GPG error: http://extras.ubuntu.com natty InRelease: File /var/lib/apt/lists/partial/extras.ubuntu.com_ubuntu_dists_natty_InRelease doesn't start with a clearsigned message, W:GPG error: http://security.ubuntu.com natty-security InRelease: File /var/lib/apt/lists/partial/security.ubuntu.com_ubuntu_dists_natty-security_InRelease doesn't start with a clearsigned message, W:GPG error: http://archive.canonical.com natty InRelease: File /var/lib/apt/lists/partial/archive.canonical.com_ubuntu_dists_natty_InRelease doesn't start with a clearsigned message, W:Failed to fetch copy:/var/lib/apt/lists/partial/extras.ubuntu.com_ubuntu_dists_natty_main_binary-i386_Packages Encountered a section with no Package: header
, W:Failed to fetch http://extras.ubuntu.com/ubuntu/dists/natty/main/i18n/Index No Hash entry in Release file /var/lib/apt/lists/partial/extras.ubuntu.com_ubuntu_dists_natty_main_i18n_Index
, W:Failed to fetch http://security.ubuntu.com/ubuntu/dists/natty-security/universe/binary-i386/Packages 0 Ok [IP: 91.189.92.166 80]
, W:Failed to fetch http://archive.canonical.com/ubuntu/dists/natty/partner/source/Sources 0 Ok
, W:Failed to fetch gzip:/var/lib/apt/lists/partial/dl.google.com_linux_earth_deb_dists_stable_main_i18n_Translation-en Encountered a section with no Package: header
, W:Failed to fetch http://archive.canonical.com/ubuntu/dists/natty/partner/binary-i386/Packages 0 Ok
, W:Failed to fetch gzip:/var/lib/apt/lists/partial/archive.canonical.com_ubuntu_dists_natty_partner_i18n_Translation-en Encountered a section with no Package: header
, W:Failed to fetch gzip:/var/lib/apt/lists/partial/security.ubuntu.com_ubuntu_dists_natty-security_multiverse_i18n_Translation-en Encountered a section with no Package: header
, W:Failed to fetch copy:/var/lib/apt/lists/partial/us.archive.ubuntu.com_ubuntu_dists_natty-updates_universe_binary-i386_Packages Encountered a section with no Package: header
, W:Failed to fetch copy:/var/lib/apt/lists/partial/packages.medibuntu.org_dists_natty_free_i18n_Translation-en Encountered a section with no Package: header
, E:Some index files failed to download. They have been ignored, or old ones used instead.

Victory! It was a router problem as you suggested - had to reload corrected firmware. Now everything is working fine. Thanks a bunch for the help!

Thanks Manfred Hampl, that solved my question.