ksort() se moque de vous ? Voilà de quoi trier sans vergogne les clés accentuées de vos tableaux :

function wd_remove_accents($str, $charset='utf-8')
{
	$str = htmlentities($str, ENT_NOQUOTES, $charset);

	$str = preg_replace('#\&([A-za-z])(?:uml|circ|tilde|acute|grave|cedil|ring)\;#', '\1', $str);
	$str = preg_replace('#\&([A-za-z]{2})(?:lig)\;#', '\1', $str);
	$str = preg_replace('#\&[^;]+\;#', '', $str);
	
	return $str;
}

function wd_unaccent_compare($a, $b)
{
    return strcmp(wd_remove_accents($a), wd_remove_accents($b));
}

$ar = array
(
    'popé' => 4,
    'épinard' => 1,
    'carotte' => 5,
    'Marrons' => 6,
    'epsilon' => 1,
    'zéro' => 2,
    'popo' => 4,
    'Étourderie' => 2
);

uksort($ar, 'wd_unaccent_compare');

Pour une explication explicative : Trier les clés accentuées d'un tableau associatif.