Do you have this line in ~/.aptitude/config

aptitude::Delete-Unused "true";

?

Search for "TRACKING UNUSED PACKAGES" in /usr/share/doc/aptitude/README
for more details.

In order to make the transition to aptitude in a more orderly way, open aptitude in full-screen mode the first time (she tries to look nice for you, too!):
# aptitude

Then type the letter "g". Aptitude will show you what its default configuration is telling it to do. The actions will be broken into several categories. Packages that it has never seen before will be on a list that says "--Packages to be removed". (If the list isn't expanded, select the list and hit Enter on your keyboard.) Take a look at the list. If you want them all to stay, select the heading and hit the + on your keyboard, which will tell it to keep all of them and upgrade them if need be.

Then type the letter "q", which will take you back to the original screen. Typing "g" again will take you to the list again, but this time taking into account your instruction to keep or upgrade the packages. Make any adjustments you want. You might want to cycle through g and q a few times to make sure everything is the way you expect. When you are satisfied, type "g" again. Aptitude will dutifully clean up your system and keep it clean for as long as you use it.

2.1 Check Aptitude's internal database

Aptitude remembers intended actions, even if you change the package states and/or configuration settings.

If you have been using another package manager since you last used Aptitude, you should check Aptitude's intended actions before proceding. Whenever in doubt, check Aptitude's intentions with a simulated ("-s") run to fix ("-f") packages that it thinks are broken. Since -s simulates it is safe to avoid the prompting by saying yes with ("-y").

# aptitude install -sfy

If Aptitude wrongly wants to remove packages, apply one of the fixes below.
[edit] 2.2 Global fix of Aptitude's internal database

Tell Aptitude to "keep-all" installed packages. This cancels all scheduled actions on all packages (including installation, removal, or upgrade).

# aptitude keep-all


Tip
Tip:
If you ever need to avoid trouble, "aptitude keep-all" restores sane behavior.

[edit] 2.3 Fix just the "automatically installed" flag

A common problem is that some packages may be wrongly marked as automatically installed. Aptitude may wrongly want to remove some of them. You can fix this by telling Aptitude to unmark ("unmarkauto") all such packages that are currently installed ("--schedule-only '~i'"). This command is more specific than "aptitude keep-all" and may be sufficient to fix the problem. It has the advantage that it does not modify any other "sticky" flags (eg "hold" or "forbid-version").

# aptitude unmarkauto --schedule-only '~i'

Aptitude tries to react immediately to changes in package states, including the "automatically installed" ("A") flag. If you want to run several successive "(un)markauto" commands to change/fix your system then you have to use "--schedule-only" to keep Aptitude from doing something unintended halfway through the operation.

If you want to be on the safe side you can always run "aptitude install -sfD" afterwards to check whether any of your previous commands has caused Aptitude to schedule unwanted actions. The "-D" option shows brief explanations of automatic installations and removals.

# aptitude install -sfD

If this shows any unwanted actions, you can always run "aptitude keep-all" to revoke all scheduled actions. Of course, this will also remove any "markauto", "hold" and "forbid-version" specifications that you may have flagged manually. If you are fine-tuning to this extent, you should probably install one of the "aptitude-doc-??" packages and check the documentation in /usr/share/doc/aptitude/html.

# aptitude keep-all

If you are running Aptitude interactively, another helpful stop-gap measure is temporarily to set a configuration file option directly with the "-o" option. (See /usr/share/doc/aptitude/html/en/ch02s04s05.html#configKeep-Unused-Pattern after installing the aptitude-doc-en package or one of the other language versions.) The term "~T" matches any package. Set the configuration file option to keep any packages marked as unused.

# aptitude -o Aptitude::Keep-Unused-Pattern='~T'