wrapping menu items with span in Drupal 6
The answer that you found is for Drupal 7 not for Drupal 6.

In Drupal 6 you can't override theme_links() for a specific target. 

You need to override theme_links() function itself to add span tag as the following code:

function sub_website_links($links, $attributes = array('class' =&gt; 'links')) {
  global $language;
  $output = '';

  if (count($links) &gt; 0) {
    $output = '&lt;ul'. drupal_attributes($attributes) .'&gt;';

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

    foreach ($links as $key =&gt; $link) {
      $class = $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']) &amp;&amp; ($link['href'] == $_GET['q'] || ($link['href'] == '&lt;front&gt;' &amp;&amp; drupal_is_front_page()))
          &amp;&amp; (empty($link['language']) || $link['language']-&gt;language == $language-&gt;language)) {
        $class .= ' active';
      }
      $output .= '&lt;li'. drupal_attributes(array('class' =&gt; $class)) .'&gt;';

      if (isset($link['href'])) {
        // Pass in $link as $options, they share the same keys.

        // check if menu id attribute is set to primary-links
        if(isset($attributes['id']) &amp;&amp; $attributes['id'] == 'primary-links') {

          // add html to link options 
          $link['html'] = true;

          // wrap text with span
          $output .= l('&lt;span&gt;' . $link['title'] . '&lt;/span&gt;', $link['href'], $link);

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

      }
      else if (!empty($link['title'])) {
        // Some links are actually not links, but we wrap these in &lt;span&gt; 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 .= '&lt;span'. $span_attributes .'&gt;'. $link['title'] .'&lt;/span&gt;';
      }

      $i++;
      $output .= "&lt;/li&gt;\n";
    }

    $output .= '&lt;/ul&gt;';
  }

  return $output;
}


Then edit page.tpl.php and add id attribute for $primary_links menu

print theme('links', $primary_links, array('id' =&gt; 'primary-links', 'class' =&gt; 'links clearfix'));