Add class to top-level ul using menu_block
Here's the trick: theme_menu_tree__MENU_NAME() and theme_menu_link().

&lt;?php
/**
 * Implements theme_menu_tree().
 */
function THEMENAME_menu_tree__MENU_NAME(&amp;$variables) {
  return '&lt;ul class="FIRST-LEVEL-CLASS"&gt;' . $variables['tree'] . '&lt;/ul&gt;';
}

/**
 * Implements theme_menu_link().
 */
function THEMENAME_menu_link__MENU_NAME(array $variables) {
  $element = $variables['element'];
  $sub_menu = '';

  if ($element['#below']) {
    // Wrap in dropdown-menu.
    unset($element['#below']['#theme_wrappers']);
    $sub_menu = '&lt;ul class="OTHER-LEVEL-CLASS"&gt;' . drupal_render($element['#below']) . '&lt;/ul&gt;';
  }
  $output = l($element['#title'], $element['#href'], $element['#localized_options']);
  return '&lt;li' . drupal_attributes($element['#attributes']) . '&gt;' . $output . $sub_menu . "&lt;/li&gt;\n";
}
?&gt;