結論: col_size_of_width_a=1.
mlterm から直接 aptitude を起動すると表示は崩れない．しかし mlterm から screen を経由して aptitude を起動した場合は罫線の表示が崩れる．mlterm のオプション termtype の値が "xterm" でも "mlterm" でも変化無し．じゃあ他の端末エミュレータではどうだ，と konsole + screen + aptitude を試したら，表示は崩れなかった．
lenny 以降の screen では Ambiguous characters 対応パッチが当たっています
とあるし (実際 apt-get source screen でソースを取得してファイルを見てみたら当該パッチが在った)，上の結果からも，これは screen ではなく mlterm の問題だな，と．
しかしなー，.mlterm/main にはそんなに手の込んだ設定は書いてないはずだがなー，と思いつつ，man mlterm を見ながら当該ファイルを見直した．結果，一番疑わしかったのは col_size_of_width_a=2. でもこれはここに書いてある通りなんだけどなー，と思いつつ，ダメモトで 2 から 1 に変更．…あれ，崩れなくなったよ．ええぇぇぇ〜〜なんだそりゃ．
ということで，ようやく screen を常用できるようになった (今頃かよ)．ただ，col_size_of_width_a=1 にしたことで，もしかしたら今度は他のアプリケーションに影響が出るのかもしれない．しばらく様子を見よう．
% apt-show-versions aptitude mlterm screen aptitude/lenny uptodate 0.4.11.8-1 mlterm/lenny uptodate 2.9.4-4 screen/lenny uptodate 4.0.3-11