Japanese Teamのunzipがインストールされて、p7zip-fullもインストールされてないにも関わらず文字化けが発生するという事でしょうか？
もしくは、p7zip-fullがなにかのソフトの依存関係によりどうしても必要だという事でしょうか？

zipアーカイブの参照や解凍にunzipよりp7zip-fullが優先して使われてしまう為に起こる昔からある問題です。
p7zip-fullをアンインストールすればunzipの方が使われるので、Japanese Teamのunzipを使っていれば文字化けしなくなります。
残るは、file-rollerの方を弄る事なんですけど、ソース弄るしかないですね（以前は某所のPPAを使ってたのだけど、13.10用のPPAはまだないです）
過去ログ見ると、Ubuntu 8.04の頃はp7zip-fullが入ってても問題なかったという記事が見られますが、なにも7zを使いたいが為にp7zip-fullを使ってるわけではなく、ある特定のソフトが依存関係を持つが為にインストールされてるのが殆どだと思います。
https://forums.ubuntulinux.jp/viewtopic.php?id=3529

なもんで、なんとかしてもらいたいと思ってる今日このごろ。