Assigning custom class to nested menu UL elements
This kind of issues should be managed by CSS, but if you realy need to override the theme_menu_tree() and define a custom ul class there, you can do that with the help of custom global variable created in theme_menu_link(). 

Not sure if it's "the right way" to do that, but works:

/**
 * Implements theme_menu_tree__[MENU NAME].
 */
function YOURTHEME_menu_tree__[MENU NAME]($variables) {
  global $level;
  $class = ($level == 1) ? 'my-class' : 'my-class-for-depth-' . $level;
  return '&lt;ul class="'.$class.'"&gt;' . $variables['tree'] . '&lt;/ul&gt;';
}

/**
 * Implements theme_menu_link__[MENU NAME].
 */
function YOURTHEME_menu_link__[MENU NAME]($variables) {

  $element = $variables['element'];
  $sub_menu = '';   

  // set the global variable in order to use it in hook_menu_tree()
  // I called it "level" to avoid confusing with the $depth
  global $level;

  if ($element['#below']) {
    $sub_menu = drupal_render($element['#below']);
    $level = 1; // set the level as first for each list with submenu
  }
  else {
    $level = $element['#original_link']['depth'];
  }
  $output = l($element['#title'], $element['#href'], $element['#localized_options']);
  return '&lt;li' . drupal_attributes($element['#attributes']) . '&gt;' . $output . $sub_menu . "&lt;/li&gt;\n";
}