I had a need to be able to do a custom menu in Drupal 7, and so I had to go looking for a way to customize the HTML output for the main menu. Unfortunately, it's REALLY hard to find a solution that works, but I stumbled across one and am posting it here so that when I need to find it again, I can get to it quickly.

Search phrases so that other people can find it as well:

• Add span tags before menu items
• arbitrary HTML in menu
• custom HTML in main menu

I hope that's all I need for the time being

OK, solution here: this forum post on drupal.org

What to do with it:

<?php
function THEMENAME_links__system_main_menu($variables){
  $links = $variables['links'];
  $attributes = $variables['attributes'];
  $heading = $variables['heading'];
  global $language_url;
  $output = '';

  if (count($links) > 0) {
    $output = '';

    // Treat the heading first if it is present to prepend it to the
    // list of links.
    if (!empty($heading)) {
      if (is_string($heading)) {
        // Prepare the array that will be used when the passed heading
        // is a string.
        $heading = array(
          'text' => $heading,
          // Set the default level of the heading.
          'level' => 'h2',
        );
      }
      $output .= '<' . $heading['level'];
      if (!empty($heading['class'])) {
        $output .= drupal_attributes(array('class' => $heading['class']));
      }
      $output .= '>' . check_plain($heading['text']) . '</' . $heading['level'] . '>';
    }

    $output .= '<ul' . drupal_attributes($attributes) . '>';

    $num_links = count($links);
    $i = 1;

    foreach ($links as $key => $link) {
      $class = array($key);

      // Add first, last and active classes to the list of links to help out themers.
      if ($i == 1) {
        $class[] = 'first';
      }
      if ($i == $num_links) {
        $class[] = 'last';
      }
      if (isset($link['href']) && ($link['href'] == $_GET['q'] || ($link['href'] == '<front>' && drupal_is_front_page()))
          && (empty($link['language']) || $link['language']->language == $language_url->language)) {
        $class[] = 'active';
      }
      $output .= '<li' . drupal_attributes(array('class' => $class)) . '>';

      if (isset($link['href'])) {
        // Pass in $link as $options, they share the same keys.
        $output .= l($link['title'], $link['href'], $link);
      }
      elseif (!empty($link['title'])) {
        // Some links are actually not links, but we wrap these in <span> for adding title and class attributes.
        if (empty($link['html'])) {
          $link['title'] = check_plain($link['title']);
        }
        $span_attributes = '';
        if (isset($link['attributes'])) {
          $span_attributes = drupal_attributes($link['attributes']);
        }
        $output .= '<span' . $span_attributes . '>' . $link['title'] . '</span>';
      }

      $i++;
      $output .= "</li>\n";
    }

    $output .= '</ul>';
  }

  return $output;
}
?>

Basically, I had to add DIV tags before and after the link, so that I could style on a left and right side to the link and make it looks like it was rounded with a drop shadow. I replaced this line:

$output .= l($link['title'], $link['href'], $link);

With This:

$output .= "<div class='before-link'></div>".l($link['title'], $link['href'], $link)."<div class='after_link'></div>";

And that did the trick to add before and after div tags to the Main Menu, allowing me to style them to my heart's content.