Спасибо за подсказку, действительно в /etc/environment помогло.
2 Kitrom,
если еще актуально - попробуйте удалить в ~/.evolution/addressbook/local/system файлы pilot-map* и pilot-sync*.
Ну или точно поможет - отхарезетете свою палм и создайте нового пользователя с новым ID в gnome-pilot, и синхронизируйтесь.
Да, кстати, не уверен, но мне кажется что и локаль CP1251 должна быть сгенерена.
Вообще решение прилипить бы куда нибудь, а то гугление очень мало дало пока тут не наткнулся.