Working with drupal theme_menu_tree

template.tpl.php

<?php
/**
 * Theme_menu_tree doesn't provide any context information
 * THIS SUCKS
 * But you can use hook_block_view_alter to change the theme wrapper
 * OUF!
 */


function MYTHEME_menu_tree(&$variables) {
 return '<ul class="nav">' . $variables['tree'] . '</ul>';
}

function MYTHEME_menu_tree__menu_top_menu(&$variables) {
 return '<ul class="nav center">' . $variables['tree'] . '</ul>';
}
//main menu (top) using the menu block module
function MYTHEME_menu_tree__menu_block__2(&$variables) {
    return '<ul class="nav main-nav nav-horizontal">' . $variables['tree'] . '</ul>';
}
//main menu (level 2 sidebar) using the menu block module
function MYTHEME_menu_tree__menu_block__1(&$variables) {
      return '<ul>' . $variables['tree'] . '</ul>';
}
function MYTHEME_menu_tree__menu_block__1__level1(&$variables) {
    return '<ul class="nav nav-list">' . $variables['tree'] . '</ul>';
}


/**
 * Implements hook_block_view_alter().
 */
function MYTHEME_block_view_alter(&$data, $block) {
  // Check we get the right menu block (side bar)
  if ($block->bid == 'menu_block-1') {
    // change the theme wrapper for the first level
    $data['content']['#content']['#theme_wrappers'] = array('menu_tree__menu_block__1__level1');
  }
}

Thanks for the insight! I have been trying to change the wrappers for hours now...
Why doesn't this ship with theme_menu_tree()? Ridiculous! 💣

Yet I had to make a few adjustments in the hook_block_view_alter() to get it up and running, as var_dump($block) yield the following output in Dupal 7.22:

stdClass Object (
    [bid] => MENUID
    [module] => system
    [delta] => MENU-NAME
    [theme] => MYTHEME
    [status] => 1
    [weight] => -7
    [region] => navigation
    [custom] => 0
    [visibility] => 0
    [pages] => 
    [title] => 
    [cache] => -1
)

...which turns the hook into:

function MYTHEME_block_view_alter(&$data, $block) {
  // Check we get the right menu block (side bar)
  if ($block->delta == 'MENU-NAME') {
    // change the theme wrapper for the first level
    $data['content']['#content']['#theme_wrappers'] = array('menu_tree__menu_block__1__level1');
  }
}

Check out this approach to get levels both in ul and li - https://gist.github.com/henrijs/6225177.

Thank you!!!

After a little bit of confusion I finally figured out what was wrong with the original post and with the comment by alexdo. I altered the code (at least for drupal 7.26) in this way:

function MYTHEME_menu_tree__menu_block__1__level1($variables) {
return '<ul class="nav nav-list">' . $variables['tree'] . '</ul>';
}

function MYTHEME_block_view_alter(&$data, $block) {
  // Check we get the right menu block (side bar)
  if ($block->delta == 'MENU-NAME') {
    // change the theme wrapper for the first level
    $data['content']['#theme_wrappers'][] = array('menu_tree__menu_block__1__level1');
  }
}

In case it's not apparent, the changes made are:

1. Removed the & from the variables parameter
2. changed to $block-> delta (as noted by alexdo)
3. changed to $data['content']['#theme_wrappers'][]

Hope this helps someone else out

Note that you can drop a block (with context) anywhere.
For example, here is an extra main menu block:

render(module_invoke('menu','block_view','main-menu'))

Thank you ! This helpful for me !

hi ! I had two menu custom , but i want to two menu same theme_wrapper ! this my code

function mytheme_block_view_alter(&$data, $block) {
    // Check We get the menu services block
    switch ($block->delta) {
        case 'menu-wordpress-services':
        case 'menu-joomla-services':
            // change the theme wrapper
            $data['content']['#content']['#theme_wrappers'] = array('menu_tree__menu_custom_services');
            break;
    }

}

function mytheme_menu_tree__menu_custom_services($vars) {
    return '<ul class="menu accordion">' . $vars['tree'] . '</ul>';
}

function mytheme_menu_link__menu_custom_services(array $vars) {
    $element = &$vars['element'];
    $sub_menu = '';
    if ($element['#below']) { 
        $element['#attributes']['class'][] = 'deeper parent';
        $sub_menu = drupal_render($element['#below']);
    }
    $output = '<p><i class="fa fa-angle-right"></i>' . l($element['#title'], $element['#href'], $element['#localized_options']) . '</p>';

    return '<li' . drupal_attributes($element['#attributes']) . '>' . $output . $sub_menu . "</li>\n";
} 

Change wrapper mytheme_menu_tree__menu_custom_services it worked but mytheme_menu_link__ menu_custom_services not work !