Все дело в юникоде и в том как PHP с ним работает. В частности когда вы получаете первый символ строки, вы забираете только его часть (так как это мультибайт стринг и все такое).
Для того что бы все корректно работало стоит использовать mb_string. Так же в php есть опеределнные нюансы в плане хранения ассоциативных массивов, в частности кодировка ключей.
Для того что бы проблем небыло совсем, стоит отказаться от использования ассоциативных массивов для этой задачи. Пример:
function build_index($words)
{
$index = [];
$current = null;
foreach($words as $word) {
$firstLetter = mb_strtolower(mb_substr($word, 0, 1, 'utf-8'), 'utf-8');
if (!$current || $current['letter'] !== $firstLetter) {
$index[] = [
'letter' => $firstLetter,
'data' => []
];
$current = &$index[count($index)-1];
}
$current['data'][] = $word;
}
return $index;
}
Демо:
ideone.com/nUSWZ3