以下コマンドでlocaleの設定を確認

$ locale -a
LANG=C.UTF-8
LANGUAGE=
LC_CTYPE="ja_JP.UJIS"
LC_NUMERIC="ja_JP.UJIS"
LC_TIME="ja_JP.UJIS"
LC_COLLATE="ja_JP.UJIS"
LC_MONETARY="ja_JP.UJIS"
LC_MESSAGES="ja_JP.UJIS"
LC_PAPER="ja_JP.UJIS"
LC_NAME="ja_JP.UJIS"
LC_ADDRESS="ja_JP.UJIS"
LC_TELEPHONE="ja_JP.UJIS"
LC_MEASUREMENT="ja_JP.UJIS"
LC_IDENTIFICATION="ja_JP.UJIS"
LC_ALL=ja_JP.UJIS

上の例だと、LC_ALLがja_JP.UJISになっており、これはLANG変数よりも優先される。
これがターミナル側の文字エンコーディング解釈と一致してない。

以下コマンドで治る。

export LC_ALL=C.UTF-8

補足

aptコマンドの出力はlocaleの影響を受ける。