As the display is updated, some text remains which should have been overwritten with blank space, but isn't. This makes the tool difficult to use, as you're left sorting out the real, current text from the gobbledygook remnants of previous screens. The fix for this problem is to change the TERM environment variable to be xterm-color rather than the default xterm. Unfortunately, this causes another issue because some tools (such as vim) have their own corruption issues when run with TERM set to xterm-color.
The solution is to put the following in your .bashrc:
if [ "$TERM" = "xterm" ]; then
alias aptitude="TERM=xterm-color sudo aptitude"
else
alias aptitude="sudo aptitude"
fi
The reason for the embedded sudo, and for the alias being defined even when TERM isn't xterm? sudo doesn't process shell aliases or functions, and so sudo must be embedded in the alias. Defining an alias even when TERM is already good is simply to preserve consistent behaviour, i.e. never needing to type sudo manually to invoke aptitude.
After doing this, aptitude now behaves correctly when searching:
Good stuff!