I have exactly the same problem. I tried the suggested methods of fixing the problem as above but to no avail.
Below is the results of what I got:-
joe@joe-desktop:~$ sudo apt-get remove ubuntu-tweak
[sudo] password for joe:
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: The package ubuntu-tweak needs to be reinstalled, but I can't find an archive for it.
joe@joe-desktop:~$ sudo apt-get purge ubuntu-tweak
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: The package ubuntu-tweak needs to be reinstalled, but I can't find an archive for it.
joe@joe-desktop:~$ sudo apt-get update
Hit
http://archive.canonical.com jaunty Release.gpg
Ign
http://archive.canonical.com jaunty/partner Translation-en_GB
Get: 1
http://archive.ubuntu.com jaunty Release.gpg [189B]
Hit
http://archive.canonical.com jaunty Release
Hit
http://gb.archive.ubuntu.com jaunty Release.gpg
Hit
http://gb.archive.ubuntu.com jaunty/main Translation-en_GB
Hit
http://security.ubuntu.com jaunty-security Release.gpg
Ign
http://security.ubuntu.com jaunty-security/main Translation-en_GB
Get: 2
http://archive.ubuntu.com jaunty Release [74.6kB]
Hit
http://archive.canonical.com jaunty/partner Packages
Hit
http://gb.archive.ubuntu.com jaunty/restricted Translation-en_GB
Hit
http://gb.archive.ubuntu.com jaunty/universe Translation-en_GB
Hit
http://gb.archive.ubuntu.com jaunty/multiverse Translation-en_GB
Hit
http://gb.archive.ubuntu.com jaunty-updates Release.gpg
Ign
http://gb.archive.ubuntu.com jaunty-updates/main Translation-en_GB
Ign
http://gb.archive.ubuntu.com jaunty-updates/restricted Translation-en_GB
Ign
http://gb.archive.ubuntu.com jaunty-updates/universe Translation-en_GB
Ign
http://gb.archive.ubuntu.com jaunty-updates/multiverse Translation-en_GB
Ign
http://security.ubuntu.com jaunty-security/restricted Translation-en_GB
Ign
http://security.ubuntu.com jaunty-security/universe Translation-en_GB
Ign
http://security.ubuntu.com jaunty-security/multiverse Translation-en_GB
Hit
http://security.ubuntu.com jaunty-security Release
Hit
http://gb.archive.ubuntu.com jaunty Release
Get: 3
http://archive.getdeb.net karmic-getdeb Release.gpg [827B]
Ign
http://archive.getdeb.net karmic-getdeb/apps Translation-en_GB
Hit
http://gb.archive.ubuntu.com jaunty-updates Release
Hit
http://security.ubuntu.com jaunty-security/main Packages
Hit
http://gb.archive.ubuntu.com jaunty/main Packages
Hit
http://gb.archive.ubuntu.com jaunty/restricted Packages
Hit
http://gb.archive.ubuntu.com jaunty/restricted Sources
Hit
http://gb.archive.ubuntu.com jaunty/main Sources
Hit
http://gb.archive.ubuntu.com jaunty/multiverse Sources
Hit
http://security.ubuntu.com jaunty-security/restricted Packages
Hit
http://security.ubuntu.com jaunty-security/restricted Sources
Hit
http://security.ubuntu.com jaunty-security/main Sources
Hit
http://security.ubuntu.com jaunty-security/multiverse Sources
Get: 4
http://archive.getdeb.net karmic-getdeb Release [7232B]
Hit
http://gb.archive.ubuntu.com jaunty/universe Sources
Hit
http://gb.archive.ubuntu.com jaunty/universe Packages
Ign
http://archive.getdeb.net karmic-getdeb Release
Hit
http://security.ubuntu.com jaunty-security/universe Sources
Hit
http://security.ubuntu.com jaunty-security/universe Packages
Hit
http://security.ubuntu.com jaunty-security/multiverse Packages
Hit
http://gb.archive.ubuntu.com jaunty/multiverse Packages
Hit
http://gb.archive.ubuntu.com jaunty-updates/main Packages
Hit
http://gb.archive.ubuntu.com jaunty-updates/restricted Packages
Hit
http://gb.archive.ubuntu.com jaunty-updates/restricted Sources
Hit
http://gb.archive.ubuntu.com jaunty-updates/main Sources
Hit
http://gb.archive.ubuntu.com jaunty-updates/multiverse Sources
Hit
http://gb.archive.ubuntu.com jaunty-updates/universe Sources
Hit
http://gb.archive.ubuntu.com jaunty-updates/universe Packages
Hit
http://gb.archive.ubuntu.com jaunty-updates/multiverse Packages
Hit
http://archive.getdeb.net karmic-getdeb/apps Packages
Get: 5
http://archive.ubuntu.com jaunty/main Sources [555kB]
Get: 6
http://archive.ubuntu.com jaunty/restricted Sources [3156B]
Fetched 633kB in 1s (488kB/s)
Reading package lists... Done
W: GPG error:
http://archive.getdeb.net karmic-getdeb Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY A8A515F046D7E7CF
W: You may want to run apt-get update to correct these problems
joe@joe-desktop:~$ sudo apt-get -f install
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: The package ubuntu-tweak needs to be reinstalled, but I can't find an archive for it.
joe@joe-desktop:~$ sudo apt-get -f remove
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: The package ubuntu-tweak needs to be reinstalled, but I can't find an archive for it.
joe@joe-desktop:~$