12時間ほど格闘してたら文字化け直りました!
sources.list書き換え → apt-get update → aptitude upgrade
→ aptitude -f install → aptitude dist-upgrade とかを繰り替えしてたら
7.10まで上がって、そしたら文字化け直ってました。

ただ依存関係がむちゃくちゃになってしまって
何かインストールしようとすると nkf と mktemp を消されますorz
パワマネ関連も挙動がおかしいです。
もう寝ます。