Na windowsie setlocale nie działa tak jak powinno, na linuxie setlocale, iconv też nie zawsze tak jak trzeba.
Spróbuj tej funkcji do sortowania albo dostosuj do swoich potrzeb:
function sort_pl($array)
{
$arr1 = array('a'=>'a!', 'c'=>'c!', 'e'=>'e!', 'l'=>'l!', 'n'=>'n!', 'o'=>'o!', 's'=>'s!', 'z'=>'z!', 'A'=>'A!', 'C'=>'C!', 'E'=>'E!', 'L'=>'L!', 'N'=>'N!', 'O'=>'O!', 'S'=>'S!', 'Z'=>'Z!');
$arr2 = array('ą'=>'a^', 'ć'=>'c^', 'ę'=>'e^', 'ł'=>'l^', 'ń'=>'n^', 'ó'=>'o^', 'ś'=>'s^', 'ź'=>'z$', 'ż' =>'z^','Ą'=>'A^', 'Ć'=>'C^', 'Ę'=>'E^', 'Ł'=>'L^', 'Ń'=>'N^', 'Ó'=>'O^', 'Ś'=>'S^', 'Ź'=>'Z$', 'Ż'=>'Z^');
// zamienia litery, które mogą być z ogonkami na "litera!"
foreach ($array as $k=>$v) $array[$k] = str_replace(array_keys($arr1), array_values($arr1), $v);
// zamienia litery z ogonkami na "litera^" lub "litera$"
foreach ($array as $k=>$v) $array[$k] = str_replace(array_keys($arr2), array_values($arr2), $v);
/* znaki zamieniane są po to, żeby była ta sama ilość znaków i właściwie sortowało,
* np: acki, ącki => a!cki, a^cki) (kolejność znaków: !, $, ^, a, b, c...)
*/
sort($array); // sortuje
//wymienia klucze z wartościami w tablicach
$arr1 = array_flip($arr1);
$arr2 = array_flip($arr2);
// przywraca właściwe litery
foreach ($array as $k=>$v) $array[$k] = str_replace(array_keys($arr1), array_values($arr1), $v);
foreach ($array as $k=>$v) $array[$k] = str_replace(array_keys($arr2), array_values($arr2), $v);
// zwraca posortowaną tablicę
return $array;
}
$tab = array( "ąćki", "śliski aą", "acki", "elegancki", "śliski aa", "ącki", "aćki");
$tab = sort_pl($tab);
print_r($tab);