Похоже, что локаль не сгенерирована. Я 2 года живу на UTF8, таких проблем никогда не встречал. -- Bacek. P.S. dpk-reconfigure locales