This can be a problem with you locales. You need to add them.
On Debian you can run dpkg-reconfigure locales and selecht the desired language.
On Ubuntu you need to add them to /var/lib/locales/supported.d/local 1 line per language, safe and then run dpkg-reconfigure locales. You can find the supported locales in /usr/share/i18n/SUPPORTED
Please see http://tlug.dnho.net/?q=node/237
This solved the problem on my Plesk 9 / Ubuntu 8 server.
Please take a look at the following Knowledge Base article:
I cannot switch the language in Webmail in my Plesk for Debian/Ubuntu. Even if I choose another language Webmail shows English. http://kb.odin.com/en/900