Я не эксперт по Юникоду, но это пробудило мое любопытство, поэтому я написал небольшой код:
http://static.bwerp.net/~adam/20100420/m.php
Кажется, здесь неплохо работает. Вы сказали, что думали, что это проблема UTF-8. Что произойдет, если вы удалите акцентированный символ?
Для потомков вот код в связанном файле:
header('Content-type: text/html; charset=utf-8');
echo '<pre>';
$s = utf8_encode("El Salvador (Rep\xfablica De El Salvao)");
echo '$s = ', $s, '<br>';
var_dump( mb_detect_encoding($s) );
$m = new Memcache;
$m->addServer('localhost', 11211);
var_dump( $m->set('foobarcheeze', $s) );
var_dump( $m->get('foobarcheeze') );
echo 'strlen($s) = ', strlen($s), '<br>';
echo 'mb_strlen($s) = ', mb_strlen($s), '<br>';
echo 'mb_strwidth($s) = ', mb_strwidth($s), '<br>';