Comment 14 for bug 64814

I also experienced this problem today. Originally I had Ubuntu 6.06 LTS on this laptop, upgraded to Edgy, then kubuntu-desktop added, then upgraded to Feisty recently.

After removing a few unnecessary applications (I honestly can't remember which at the moment sorry, mostly Gnome related though I think) via Adept, the following came up every time I ran apt-get:

Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
  knetwalk kpat kolf ksokoban blinken krec korn kscd krita-data kshisen kmoon
  kmahjongg klaptopdaemon ksig ksim kwifimanager kcharselect python2.4-dev
  kjumpingcube kdeartwork-style kdeartwork-misc kcoloredit artsbuilder kdessh
  kanagram ktip libpth20 kmrml katomic libcvsservice0 kleopatra
  kdegames-card-data kruler ktux klettres python-at-spi kgoldrunner
  kbackgammon kpoker dirmngr kdepim-kfile-plugins kpackage kenolaba
  wlassistant kblackbox kdebase atlantikdesigner libmagick++9c2a
  konsolekalendar klatin libkexif1 kfloppy kstars ttf-dustin ksame kbruch
  kpager libkdegames1 kde-core kcalc krita keduca libboost-thread1.33.1
  kdeedu-data kdemultimedia-kappfinder-data libnspr4-0d kdeartwork-theme-icon
  kweather kmplot kalzium ksirc librss1 klinkstatus libboost-date-time1.33.1
  klickety kpovmodeler ksayit kmouth kalarm noatun-plugins kworldclock
  kalzium-data mpeglib kdewebdev kdegames kicker-applets amor kdict ktouch
  ktnef khexedit kdeaccessibility kedit kbounce kvoctrain kdetoys
  kimagemapeditor atlantik tidy libtidy-0.99-0 libexif-dev libgphoto2-2-dev
  libusb-dev kwordquiz kview libdb4.3++c2 ktron ttf-sjfonts ksync cvs
  kdenetwork libtiff-tools kttsd kdeartwork-emoticons dcoprss ksysv kwin4
  kdewallpapers kuser klettres-data kdeaddons kreversi kdf libksba8 kspaceduel
  kig libjpeg62-dev gnupg-agent libxul0d juk noatun klines fifteenapplet
  kdemultimedia kfaxview kstars-data edict lskat zlib1g-dev
  kaddressbook-plugins libarts1-mpeglib kviewshell kgamma kfilereplace
  kommander kdeutils kdegraphics kaboodle khangman gtk2-engines-gtk-qt
  libindex0 libmozjs0d kdeartwork-theme-window ksmiletris libarts1-audiofile
  kxsldbg quanta kbattleship kiconedit kdeadmin kpilot kasteroids
  myspell-en-za kfouleggs libmal1 libkdeedu3 libkgantt0 knewsticker ksnake
  kdelibs kappfinder eyesapplet kdat indi libxul-common kdelirc kpercentage
  superkaramba kjots kfax secpolicy ksirtet kmines kdvi kget pinentry-qt
  mscompress libgtkglext1 kgpg konquest kate-plugins libboost-python1.33.1
  kolourpaint libnss3-0d gpgsm gnupg2 kdeaddons-kfile-plugins libarts1-xine
  python-orca-brlapi ktuberling libltdl3 kturtle kaudiocreator ktimer
  quanta-data kmid kteatime kverbos kdeartwork kodo
Use 'apt-get autoremove' to remove them.

Ouch...

I removed the /var/lib/apt/extended_states file as suggested above, and the problem seems to have gone away. I agree this is something that needs resolving though, if I had been a newbie just following on screen instructions I'd have nuked half my system!