I see a problem is in function sanitize_title() defined in functions-formatting.php file.
this function strips all non-english characters. BTW you can optimize it if replace
function sanitize_title($title) {
$title = strtolower($title);
$title = preg_replace('/&.+?;/', '', $title); // kill entities
$title = preg_replace('/[^a-z0-9 -]/', '', $title);
$title = trim($title);
$title = preg_replace('/\s+/', '-', $title);
$title = preg_replace('|-+|', '-', $title);
return $title;
}
Also line 278 in wp-blog-header.php strips all non-latin letters from category name, but the main problem is the way PHP and MySQL handles utf8 charset.