I'm not a Unicode expert, but this piqued my curiosity so I wrote a little code:
http://static.bwerp.net/~adam/20100420/m.php
Seems to work reasonably well, over here. You said you thought it was a UTF-8 issue. What happens if you remove the accented character?
For posterity, here's the code in the linked file:
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>';