How to correctly sort on accented letters when using the Lexicon module?
If you want to find out whether or not the patch is applied correctly, open up lexicon.admin.inc and look for this code

if ($form_state['values']['lexicon_clear_filter_cache_on_submit'] == 1) {
 _lexicon_clear_filter_cache(NULL, TRUE);
function lexicon_alphabet_form($form, &amp;$form_state) {
 '#type' =&gt; 'textarea',
 '#title' =&gt; t('Enter all the digits of your alphabet, in the correct order.'),
 '#default_value' =&gt; implode(' ', variable_get('lexicon_digits', range('0', '9'))),
 '#description' =&gt; t("Separate the digits by a blank. If you don't want terms to start with digits, leave this blank."),
);


If the patch has been applied successfully it will look like this

function lexicon_alphabet_form($form, &amp;$form_state) {
  '#type' =&gt; 'textarea',
  '#title' =&gt; t('Enter all the digits of your alphabet, in the correct order.'),
  '#default_value' =&gt; implode(' ', variable_get('lexicon_digits', range('0', '9'))),
  '#description' =&gt; t('Separate the digits by a blank. If you don\'t want terms to start with digits, leave this blank.'),
  '#rows' =&gt; 1,
 );

$form['transliteration'] = array(
  '#type' =&gt; 'textarea',
  '#title' =&gt; t('Enter transliteration rules used for indexing terms.'),
  '#default_value' =&gt; _lexicon_transliteration_ruleset_encode(variable_get('lexicon_transliteration', array())),
  '#description' =&gt; t('Use the syntax "é:e,è:e,ê:e,...". Transliteration rules are only applied internaly for indexing. Terms are displayed unchanged.'),
  '#rows' =&gt; 1,
);


Notice inside the function lexicon_alphabet_form, in the '#description' attribute don't changed to don\'t and also the $form['transliteration'] was added in the patch. If you don't see these changes inside lexicon.admin.inc then the patch was not applied correctly. If you do, then the patch did not fix your problem. Hopefully this will help you narrow down where the problem is.

EDIT:

If the patch has been applied successfully,  go into the lexicon administration page and set the transliteration rules. Looking at the patch, it looks like it added a textfield for defining the rules you want to use in the following syntax é:e,è:e,ê:e,...