Recently, doing an `aptitude update; aptitude upgrade` broke with the above error. The output looked like this:
~$ sudo aptitude upgrade
Reading package lists… Done
Building dependency tree… Done
Reading extended state information
Initializing package states… Done
Reading task descriptions… Done
Building tag database… Done
The following packages have been kept back:
apache2 apache2-mpm-prefork apache2-utils apt cpp g++ gcc gnupg
initscripts libapache2-mod-php4 libapache2-svn libsasl2
linux-image-2.6-686-smp mutt netbase nfs-common ntp ntp-simple php4
php4-common python reportbug subversion subversion-tools sysvinit
0 packages upgraded, 0 newly installed, 0 to remove and 25 not upgraded.
Need to get 0B of archives. After unpacking 0B will be used.
aptitude: symbol lookup error: aptitude: undefined symbol: _ZN9pkgPolicyD2Ev
I ended up running `apt-get install apt` and it upgraded apt/aptitude to a newer version and my problem went away. Funky.