Aptitude no longer removes unused dependencies.

[Lex Hider]

One of my favourite features of aptitude is that it can keep track of
which packages have been installed solely as dependencies for other
packages and remove these packages when they are no longer needed.

It appears that aptitude in hoary is no longer doing this.

e.g. if I hit 'M' on a bunch of already installed packages in aptitude
it won't offer to remove any, even if I hit 'M' on every installed
package.

I would really like to get the old behaviour back. That way you can just
keep track of a handful of packages that you explicitly want [e.g. you
may just want ubuntu-base ubuntu-desktop and a few other necessary apps
and let aptitude sort out the dependencies for all of this].

Lex.

Here's a relevant post from the archives:
http://lists.ubuntu.com/archives/ubuntu-users/2004-October/008445.html