Takashi Chiba への返信。

今手元の Ubuntu 環境だと Ubuntu 18.10 amd64 環境しか無いのですが，この環境に Freeplane をパッケージ導入してみたところ文字化けはしないようです．
試したバージョンは
> $ dpkg-query -W freeplane
> freeplane 1.6.15-1
です．

Freeplane 自体が起動するのであればフォントが足りない可能性がありそうです．
/var/log/apt/history.log* で Remove: の項目を探してみると該当するものがあるかもしれません．