I have been look for a very long time let's focus on a fix for your problem but found nothing so everyone is going to be my last hope!

I am attempting to develop a new CSS3 menu on the Wordpress 3 site that I am focusing on. I will have to extend the default menu mark-up although not sure how.

This is actually the tag I am using within the theme to output recption menus right now:

<?php wp_nav_menu( array( 'container_class' => 'menu-header', 'theme_location' => 'primary' ) ); ?>

Right now my default menu mark-up appears like this:

<div class="menu-header">
 <ul id="menu-main-menu" class="menu">
  <li id="menu-item-62" class="menu-item menu-item-type-post_type current-menu-item page_item page-item-43 current_page_item menu-item-62"><a href="#">Top Level Menu Item</a></li>
  <li id="menu-item-70" class="menu-item menu-item-type-post_type menu-item-70"><a href="#">Top Level Menu Item</a>
   <ul class="sub-menu">
    <li id="menu-item-71" class="menu-item menu-item-type-taxonomy menu-item-71"><a href="#">Sub Level Menu Item</a></li>
   </ul>
  </li>
  <li id="menu-item-220" class="menu-item menu-item-type-post_type menu-item-220"><a href="#">Top Level Menu Item</a></li>
  <li id="menu-item-129" class="menu-item menu-item-type-post_type menu-item-129"><a href="#">Top Level Menu Item</a>
   <ul class="sub-menu">
    <li id="menu-item-206" class="menu-item menu-item-type-post_type menu-item-206"><a href="#">Sub Level Menu Item</a></li>
    <li id="menu-item-207" class="menu-item menu-item-type-post_type menu-item-207"><a href="#">Sub Level Menu Item</a></li>
    <li id="menu-item-200" class="menu-item menu-item-type-post_type menu-item-200"><a href="#">Sub Level Menu Item</a></li>
   </ul>
  </li>
  <li id="menu-item-243" class="menu-item menu-item-type-post_type menu-item-243"><a href="#">Top Level Menu Item</a></li>
 </ul>
</div>

I have to add 2 div's around each <ul class="sub-menu">...</ul> And So I would want the objective-as much as seem like this:

<div class="menu-header">
 <ul id="menu-main-menu" class="menu">
  <li id="menu-item-62" class="menu-item menu-item-type-post_type current-menu-item page_item page-item-43 current_page_item menu-item-62"><a href="#">Top Level Menu Item</a></li>
  <li id="menu-item-70" class="menu-item menu-item-type-post_type menu-item-70"><a href="#">Top Level Menu Item</a>
   <div class="sub-menu-container">
    <div class="submenu">
     <ul class="sub-menu">
      <li id="menu-item-71" class="menu-item menu-item-type-taxonomy menu-item-71"><a href="#">Sub Level Menu Item</a></li>
     </ul>
    </div>
   </div>
  </li>
  <li id="menu-item-220" class="menu-item menu-item-type-post_type menu-item-220"><a href="#">Top Level Menu Item</a></li>
  <li id="menu-item-129" class="menu-item menu-item-type-post_type menu-item-129"><a href="#">Top Level Menu Item</a>
   <div class="sub-menu-container">
    <div class="submenu">
     <ul class="sub-menu">
      <li id="menu-item-206" class="menu-item menu-item-type-post_type menu-item-206"><a href="#">Sub Level Menu Item</a></li>
      <li id="menu-item-207" class="menu-item menu-item-type-post_type menu-item-207"><a href="#">Sub Level Menu Item</a></li>
      <li id="menu-item-200" class="menu-item menu-item-type-post_type menu-item-200"><a href="#">Sub Level Menu Item</a></li>
     </ul>
    </div>
   </div>
  </li>
  <li id="menu-item-243" class="menu-item menu-item-type-post_type menu-item-243"><a href="#">Top Level Menu Item</a></li>
 </ul>
</div>

Does anybody understand how to do that please?

Recption menus markup is produced in wordpress-includes/classes.php with Walker class, particularly class Walker_Page extends Walker {

Should you examine the functions within the class you can observe in which the actual markup is produced.

http://codex.wordpress.org/Function_Reference/Walker_Class