aptitude show wrong package state

Status changed to 'Confirmed' because the bug affects multiple users.

Same here, for example searching for libapr gives the following (wrong results, libapr1 is installed):
# aptitude search libapr
p libapr1 - Apache Portable Runtime Library
p libapr1-dbg - Apache Portable Runtime Library - Debugging Symbols
p libapr1-dev - Apache Portable Runtime Library - Development Headers
p libapreq2 - generic Apache request library
p libapreq2-dev - generic Apache request library - development files
p libapreq2-doc - generic Apache request library - documentation
p libapron - runtime libraries for APRON
p libapron-dev - an abstract interpretation library
p libapron-ocaml - runtime libraries for APRON (OCaml interface)
v libapron-ocaml-b3on5 -
p libapron-ocaml-dev - an abstract interpretation library (OCaml interface)
v libapron-ocaml-dev-b3on5 -
v libapron-ocaml-dev-q5lr0 -
v libapron-ocaml-q5lr0 -
i A libaprutil1 - Apache Portable Runtime Utility Library
p libaprutil1-dbd-freetds - Apache Portable Runtime Utility Library - FreeTDS Driver
p libaprutil1-dbd-mysql - Apache Portable Runtime Utility Library - MySQL Driver
p libaprutil1-dbd-odbc - Apache Portable Runtime Utility Library - ODBC Driver
p libaprutil1-dbd-pgsql - Apache Portable Runtime Utility Library - PostgreSQL Driver
p libaprutil1-dbd-sqlite3 - Apache Portable Runtime Utility Library - SQLite3 Driver
p libaprutil1-dbg ...

Sorry forgot to mention my Ubuntu version. Here it is:
# lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 11.10
Release: 11.10
Codename: oneiric

For me this issue is even more serious.
When starting aptitude without parameters a lot of packages are shown as new. Pressing "f" hides them but only until I do something (for example press "u"). The number of (false) new packages changes every time (at startup or pressing "u").
Also, there are problems with the upgradable packages which are also incorrectly shown. One time I was trying to do an upgrade and aptitude wanted to uninstall more then 100 packages.
Another problem is that lots of packages are shown twice.

I used to use aptitude for everything, but in this state it is completely unusable.

This appears to be the same issue as bug 831768. Short version: multiarch support, enabled by default in Ubuntu 11.10, causes each architecture of a package to have an entry in the package database. Aptitude is not multiarch aware and displays one at random. It appears that at least a decent workaround might be in place for Precise, but no hope for Oneiric.

Not marking as duplicate because to the best of my limited launchpad knowledge, this one would then be hidden - and anyone searching for symptoms related to package states or searching would be hard pressed to stumble upon 831768.

I'm seeing this in Precise still:

dpkg output to show packages are installed:
$ sudo dpkg -l | grep fgl
ii fglrx-amdcccle-updates 2:8.911-0ubuntu1 Catalyst Control Center for the AMD graphics accelerators
ii fglrx-updates 2:8.911-0ubuntu1 Video driver for the AMD graphics accelerators

Then a fairly non-specific search for fglrx:

$ sudo aptitude search fglrx
p fglrx - Video driver for the AMD graphics accelerators
p fglrx-amdcccle - Catalyst Control Center for the AMD graphics accelerators
p fglrx-amdcccle-updates - Catalyst Control Center for the AMD graphics accelerators
v fglrx-control -
v fglrx-control -
p fglrx-dev - Video driver for the AMD graphics accelerators (devel files)
v fglrx-driver -
v fglrx-driver -
v fglrx-driver-dev -
v fglrx-driver-dev -
p fglrx-updates - Video driver for the AMD graphics accelerators
p fglrx-updates-dev - Video driver for the AMD graphics accelerators (devel files)

If I search for fglrx-updates specifically though, it shows up as installed:

$ sudo aptitude search fglrx-updates
i fglrx-updates - Video driver for the AMD graphics accelerators ...

Here is another data point, as this is affecting me: Depending on the search it displays 'p' or 'i', and when you show it displays 'installed':

jonathan@kripke:~$ aptitude search xscreensaver-screensaver-bsod
i xscreensaver-screensaver-bsod - BSOD hack from XScreenSaver
jonathan@kripke:~$ aptitude search screensaver
p gnome-screensaver - GNOME screen saver and locker
p gnome-screensaver-flags - Screensaver for GNOME with flags of the world.
p kscreensaver - Additional screensavers for KScreenSaver
p kscreensaver-xsavers - xscreensaver support for KScreenSaver
p kscreensaver-xsavers-extra - universe xscreensaver support
p kscreensaver-xsavers-webcollage - webcollage screensaver support for KScreenSaver
p libkscreensaver5 - library of the KDE Screensaver system
p libopengl-xscreensaver-perl - Perl module for writing OpenGL-based XScreenSaver hacks
p libxcb-screensaver0 - X C Binding, screensaver extension
p libxcb-screensaver0-dbg - X C Binding, screensaver extension, debugging symbols
p libxcb-screensaver0-dev - X C Binding, screensaver extension, development files
p screensaver-default-images - Wallpapers for image processing screensavers
p ubuntustudio-screensaver - Ubuntu Studio screensaver
p unicode-screensaver - screensaver displaying unicode characters
p xscreensaver - Automatic screensaver for X
p xscreensaver-data - data files to be shared among screensaver frontends
p...

commit 097f91e9846634bef4f3e01b8dfa101bb298d0ee
Author: Daniel Hartwig <email address hidden>
Date: Thu Mar 15 23:06:08 2012 +0800

    Use full name (i.e. architecture) with ?name sort policy

    A package's full name includes the architecture, so consider
    this when using sort policies.

Problem was aptitude considering multi-arch packages to be the same. You would get varying results for the status based upon which package it encountered first in the search.

Here libc-bin was reported incorrectly:

$ aptitude-0.6.5 search libc-bin$ libc6$
p libc-bin - Embedded GNU C Library: Binaries
i A libc6 - Embedded GNU C Library: Shared libraries

The full list shows this ok:

$ aptitude search libc-bin$ libc6$
i libc-bin - Embedded GNU C Library: Binaries
p libc-bin:armel - Embedded GNU C Library: Binaries
i libc6 - Embedded GNU C Library: Shared libraries
i A libc6:armel - Embedded GNU C Library: Shared libraries

This bug was fixed in the package aptitude - 0.6.6-1ubuntu1

---------------
aptitude (0.6.6-1ubuntu1) precise; urgency=low

  * Resynchronise with Debian. Remaining changes:
    - debian/05aptitude: Never autoremove kernels.
    - Drop aptitude-doc to Suggests.
    - 03_branding: Ubuntu branding.
    - 04_changelog: Take changelogs from changelogs.ubuntu.com.
    - 11_ubuntu_uses_sudo: Fix status line of 'Become root' menu entry to
      not refer to su.
    - 12_point_manpage_to_doc_package: Point Finnish manpage to the correct
      place for further info.
    - 14_html2text_preferred: Switch back to html2text in favor of elinks,
      since html2text is in main and elinks isn't.
    - no-google-mock: Don't use google-mock as it and libgtest-dev are in
      universe.

aptitude (0.6.6-1) unstable; urgency=low

  * New upstream release.

    - Basic multi-arch support. See NEWS for details.

      + add search terms ?architecture and ?multiarch;
      + add grouping policy 'architecture';

      (Closes: #659079, #661744)
      (LP: #454941, #845136, #884945, #904486)

    - Apply patch from Ubuntu to fix build -D_FORTIFY_SOURCE=2 errors.
      Thanks to Colin Watson and Michael Vogt (Closes: #497539)

    - Remove GTK+ menu entry for minesweeper. (Closes: #552522)

    - Hack to prevent debug messages dumping to the screen (Closes: #651748)

    - Fix '?action(upgrade)' and others (were finding kept
      packages instead). Thanks to 'Rogier' for the patch (Closes: #603862)

    - List update errors are reported. (Closes: #451137)

    - List update now runs APT::Update hooks. (Closes: #476399)

    - Actually silence progress messages with '-q2'. (Closes: #141719)

    - Fix various locking issues:

      + '[auto]clean' locks /var/cache/apt/archives;
      + 'update' locks /var/lib/apt/lists; (Closes: #653479)

    - Fix 'priority' cost level in resolver. The values should
      have been negated but were not. Thanks to Modestas Vainius
      for this one. (Closes: #608786)

    - Fix some help and prompt strings which wrongly included
      localized names for commands such as 'why'. (Closes: #486615)

    - Change ordering of top-level sections to match the order
      in aptitude::Sections::Top-Sections. The default order
      is now: main, contrib, non-free. (Closes: #181997)

    - Improve error messages when parsing grouping policies to
      use the user-visible names, rather than the internal
      names. (Closes: #231595)

    - Change default width of %D, %I, %o, and %Z. Thanks to
      Michał Kułach for this one. (Closes: #599209) (LP: #741417)

    - Change default width of %V, %v to 14. This greatly increases the
      number of versions which will display completely. (Closes: #624542)

    - 'versions' now groups it's results by 'package:arch' instead of
      'package'.

    - Cleared up grouping, sorting policy error messages.
      (Closes: #231595)

    - Minor correction to the user's manual. (Closes: #365485)

    - Translation updates:

      + Brazilian Portuguese (Closes: #483964)
      + Hungarian (Closes: #592468)
      + Polish (Closes: #659803)
      + Russian (Closes: #662624)

  * No longer suppl...