hito様、ありがとうございます。

＞ もしVNC等を利用できるのであれば、リモート接続だと問題が再現しない、といった特徴はないでしょうか？

問題の発生しているマシンでvinoを起動し、別のマシンからremminaを使ってアクセスしてみました。
結果、remminaの画面でも文字化けが発生しました。
（なお、remminaを動かしたマシン自身は文字化けが発生しないことを確認しております。）

＞ 問題なかったタイミングと現在で、利用しているカーネルに変化はないでしょうか？
＞ もし変化があったようなら、古いカーネルに戻すと回復しないでしょうか？

/var/log/dpkg.log を確認いたしましたところ、問題に気づいた日（4月26日）以前で最後にカーネルのアップデートが実行されたのは4月14日で、しばらく前でした。
いずれにしても古いカーネルに戻してみようと思いますが、申し訳ございません、どのような手順で戻すことができますでしょうか。

問題の発生しているマシンは、当初 ubuntu-ja-14.04-desktop-amd64 をインストールしましたが、無線LANのドライバに不具合があってカーネルをバージョンアップする必要があったため、次のコマンドで 14.04.2 相当のカーネルに更新しておりました。（当該マシンはUEFI環境です。）

sudo apt-get install linux-generic-lts-utopic xserver-xorg-lts-utopic libegl1-mesa-drivers-lts-utopic xserver-xorg-video-all-lts-utopic xserver-xorg-input-all-lts-utopic linux-signed-generic-lts-utopic

その後、アップデートマネージャから促されるたびにカーネルを更新し、現在は 3.16.0-34-generic #47~14.04.1 がインストールされております。

古いカーネルに戻してみようと、先のカーネルバージョンアップの際の sudo 以下をそのまま実行しましたが、「既に最新バージョンです」とのメッセージが出て、古いバージョンに戻せませんでした。

カーネル関係のパッケージを個別にバージョン指定して・・・と思い、関係するパッケージを確認するために dpkg --list を実行しましたところ、次のとおりでした。（カーネル関係と思われるものを抜粋しております。）

linux-generic-lts-utopic                              3.16.0.34.27                                        amd64        Complete Generic Linux kernel and headers
linux-headers-3.16.0-34                               3.16.0-34.47~14.04.1                                all          Header files related to Linux kernel version 3.16.0
linux-headers-3.16.0-34-generic                       3.16.0-34.47~14.04.1                                amd64        Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
linux-headers-generic-lts-utopic                      3.16.0.34.27                                        amd64        Generic Linux kernel headers
linux-image-3.16.0-34-generic                         3.16.0-34.47~14.04.1                                amd64        Linux kernel image for version 3.16.0 on 64 bit x86 SMP
linux-image-extra-3.16.0-34-generic                   3.16.0-34.47~14.04.1                                amd64        Linux kernel extra modules for version 3.16.0 on 64 bit x86 SMP
linux-image-generic-lts-utopic                        3.16.0.34.27                                        amd64        Generic Linux kernel image
linux-signed-generic-lts-utopic                       3.16.0.34.27                                        amd64        Complete Signed Generic Linux kernel and headers
linux-signed-image-3.16.0-34-generic                  3.16.0-34.47~14.04.1                                amd64        Signed kernel image generic
linux-signed-image-generic-lts-utopic                 3.16.0.34.27                                        amd64        Signed Generic Linux kernel image

バージョン番号を見ますと、3.16.0.34.27 と 3.16.0.34.47 が混在しているようにも思えまして、どのパッケージを、どのバージョンまで、どのようなコマンドで戻すことができるのか、わかりかねてしまいました。

ご教示いただけましたら幸いに存じます。
なにとぞよろしくお願い申し上げます。

なお、グラフィックドライバに関係するかもしれないとのこと、問題の発生しているマシンは Lenovo E450 で CPU は i5-5200U、グラフィックはCPU内蔵のGPU（Intel HD Graphics 5500）を使用しております。