vncserverの環境はvncserverを起動させた時のシェル環境を引き継ぎますので、それぞれのシェル（日本語環境化させたデスクトップ上やttyな仮想コンソール、vncserverを起動させるシェル、vnc接続させたリモートのLXDE？デスクトップ、などなど）で「locale」コマンドを実行して、ロケールの状態を確認してみると良いかと思います。

一つ情報として…。
「Language Support」や「User Accounts」でユーザーのロケールを変更するとAccountsServiceの設定ファイルと「~/.pam_environment」にロケール設定が書き込まれますが、以前はttyな仮想コンソールなどで使用されていた「~/.pam_environment」がUbuntu 13.10では「書き込みはされるが使われはしない」といったことになっているみたいです。
なので、システムのデフォルトが英語環境の場合ですと、vncserverを起動するシェルによっては日本語化されなくなっています。
（デスクトップセッションのほうはディスプレイマネージャーのLightDMがAccountsServiceの情報を使用するので日本語化されます）

で、日本語ロケール化が行き渡っていない場合の対処法を挙げると、
　・「Language Support」でシステムワイドに設定する。
　・ttyな仮想コンソールなども日本語化させたい場合は「~/.profile」にロケールの環境変数設定を書き足す。（試していませんが、おそらく反映される）
　・VNC狙い撃ちで日本語化させたい場合は「~/.vnc/xstartup」にロケールの環境変数設定を書き足す。
といった辺りになるのではないかと思います。