GNOME не юзаю, но все же посмотри кодировки в ГНОМовских configах.
Также проветь наличие каталога ru в папке locale (точно не знаю,
по кр. мере в КДЕ так). Если все проги писаны с gettext, то что-то
подобное должно присутствовать. Скорее всего где-то лмнк указывает
вместо русского default (en).