The potential issue here is that somehow aptitude's perception of the package cache was off somehow. I don't know why it thought kdebase needed to be removed, but it shouldn't do that.
No, the behavior wasn't repeatable. Once I had manually installed the packages again, aptitude was aware they were supposed to be installed.
Aptitude actually removed a bunch of stuff that I manually re-installed in the line below where it says:
"kitterma@ kitterman: /var/run$ sudo apt-get install crystalcursors kdebase kappfinder"
The potential issue here is that somehow aptitude's perception of the package cache was off somehow. I don't know why it thought kdebase needed to be removed, but it shouldn't do that.
No, the behavior wasn't repeatable. Once I had manually installed the packages again, aptitude was aware they were supposed to be installed.