https://bugs.launchpad.net/ubuntu-jp-improvement/+bug/191250

を見て頂くと良いかなぁと思います。

現状では VTE_CJK_WIDTH=1 しておけばとりあえずlibvteをバックエンドにするものは動作していて、その設定を行う設定補助ツールが必要かなぁとかそんな感じで止まっています。

カーソル位置のズレは、9.10あたり以降のlibvteだと直っているような気がします。
10.04のLive環境で試してみて頂けないでしょうか？

# 少なくとも自分の環境のEmacsとvimではこのところ問題に遭遇した記憶がないため、Readlineとかそのあたりの別の問題はありえるかなぁと推定しています。

hito様
10.04 ではカーソルと表示のずれは無くなりました。
環境変数のみではダメで上のリンク先に書かれている様に --disable-factory が必要でした。

yama様
mlterm でも表示は正常で、カーソルの位置と表示のずれが問題でした。
私は ac オプションではなく
http://d.hatena.ne.jp/pair/20091127/1259304433
を参考に .mlterm/main の設定で対応しました。
ちなみに -ac 2 でも 表示位置とカーソルのずれは直りません。
たぶん 10.04 なら gnome-terminal 同様に直るかな。

とりあえず新しい libvte では問題は解決しそうなので、安心しました。
(libvte 絡めてググるといろいろ出てきますね）
あとは暇なときに 10.04 をクリーンインストールかなぁ（ちょっと気が重い）。
有用な情報ありがとうございました。