お世話になります。

ubuntu 14.04 (x86_64) の EUC-JP 環境で nmcli を実行すると字化けが起きます。具体的には http://www.ubuntulinux.jp/download/ja-remix の 14.04 を clean install 後
    /var/lib/locales/supported.d/local に「ja_JP.EUC-JP EUC-JP」という行を追加して
    locale-gen ja_JP.EUC-JP
を実行して EUC-JP locale を作成しました。その上で
    env LANG=ja_JP.EUC-JP gnome-terminal
で新たに起動した terminal window で
    nmcli con list
を実行すると1行目のタイトルと未接続の部分が字化けします。

例えば、UTF-8 環境では

名前                      UUID                                   タイプ            タイムスタンプ-リアル
HomeWLan                  620877bf-bd04-4457-899a-795e353f458c   802-11-wireless   2016年03月14日 11時59分57秒
WiredDhcp                 1e7eb35c-1b35-4699-8751-8c4099f4e034   802-3-ethernet    接続していない

という出力されるのに EUC-JP では1行目全体と3行目の「接続していない」の部分が字化けします。2行目の「月日時分秒」は正常に表示されます。
（locale category の差でしょうか？）
また、他のコマンド(ls /nonexist とか）では EUC-JP でもエラーメッセージが日本語で正しく表示されます。
strace で nmcli の実行過程の open を調べるてみると /usr/share/locale-langpack/ja/LC_MESSAGES/NetworkManager.mo は open できています。

どこか私の作業に問題が有ったのでしょうか？それとも nmcli の bug でしょうか？
よろしくお願いします。