Estes não são documentados. Meu palpite é que a é para uma instalação automática, u é para uma atualização (automática?) E b é para pacotes instalados para corrigir pacotes quebrados.
Isso significaria que debfoster está removendo pacotes que não deveria, observe que o site diz:
As of 2006-01-01, debfoster is officially deprecated.
Possivelmente isso tenha desenvolvido erros ao longo dos anos devido a mudanças no sistema apt . Você pode confirmar isso fazendo aptitude search '~b' depois de usar debfoster (listará pacotes quebrados).
Observe que apt agora suporta um sinalizador automático para pacotes de dependência e tem apt-get autoremove . Com o aptitude, você também pode fazer aptitude remove '~g' .
Atualizar
Brincando com o aptitude, acontece que, se eu pressionar ? quando obtiver o prompt Do you want to continue? [Y/n/?] , recebo a seguinte mensagem:
In the list of actions to be performed, some packages will be followed by one or
more characters enclosed in braces; for instance: "aptitude{u}". These
characters provide extra information about the package's state, and can include
any combination of the following:
'a': the package was automatically installed or removed.
'b': some of the package's dependencies are violated by the proposed changes.
'p': the package will be purged in addition to being removed.
'u': the package is being removed because it is unused.
Portanto, parece que b é para um pacote quebrado. Embora, no seu caso, parece ser um bug que é exibido se não houver nada quebrado. Não consigo recriar o problema, mas aptitude tenta reinstalar os pacotes que eu removo com apt-get sem nada entre chaves.
Observe também que aptitude keep-all é provavelmente mais seguro do que remover /var/lib/aptitude/pkgstates