I did it, with the help of this answer:
http://magento.stackexchange.com/questions/3560/how-to-sort-categories-as-they-are-shown-in-admin

New code:

    <?php 
     
     // Create get_string_between function
     function get_string_between($string, $start, $end){
        $string = ' ' . $string;
        $ini = strpos($string, $start);
        if ($ini == 0) return '';
        $ini += strlen($start);
        $len = strpos($string, $end, $ini) - $ini;
        return substr($string, $ini, $len);
     }
     
     // Get menu items
     $menu = $this->getLayout()->createBlock('cms/block')->setBlockId('main_menu')->toHtml();
     $menu = get_string_between($menu, '<p class="menu">', '</p>');
     $menuParts = explode("--", $menu);
     $isCategory = false;
     
     // $testArray = array();
     
     // Set integer variables
     $i = 0;
     $i2 = 0;
     $level = 0;
     
     // Start menu
     echo '<nav id="nav">';
     
     if ( !empty($menuParts) )
     {
     
         echo '<ol class="nav-primary">';
         
         foreach ( $menuParts as $part )
         { 
         ?>
            
            <?php // Create level 0 menu items ?>     
             <li class="level<?php echo $level; ?> nav-<?php echo $i;
             
                 if ( $i == 0 ) 
                 { 
                    echo ' first';
                 }
                 else if ( $i == (count($menuParts) - 1) ) 
                 { 
                     echo ' last';
                 } 
                 
                 $fullUrl = get_string_between($part, '<a', '/a>');
                 
                 // Dynamic Link
                 if ( strpos($part, 'widget') !== false )
                 {
                     $name = get_string_between($fullUrl, '<span>', '</span>');
                     $_category = Mage::getResourceModel('catalog/category_collection')
                            ->addFieldToFilter('name', $name)
                            ->getFirstItem();
                            
                     // Category Link
                     if ( $_category->getId() != null )
                     {
                         $_catUrl = $_category->getUrl();                 
                         $_catName = $_category->getName();
                        
                         if ( $_category->hasChildren() )
                         { 
                             echo ' parent';
                             $_catHasChildren = 'has-children';
                         }
                         else
                         {
                             $_catHasChildren = '';
                         }
                         
                         $isCategory = true;
                     }
                     // CMS Page Link
                     else
                     {
                        $_catUrl = get_string_between($fullUrl, 'href="', '">');
                        $_catHasChildren = '';
                        $_catName = get_string_between($fullUrl, '<span>', '</span>');
                        
                        $isCategory = false;
                     }
                 }
                 // Static Link
                 else 
                 {
                    $_catUrl = get_string_between($fullUrl, 'href="', '">');
                    $_catHasChildren = '';
                    $_catName = get_string_between($fullUrl, '">', '<');
                    
                    $isCategory = false;
                 }
                 
                 // array_push($testArray, $fullUrl);
                 
             ?>"> 
             
                    
                <?php // Echo anchor tag ?>
                <a href="<?php echo $_catUrl ?>" class="level<?php echo $level; ?> <?php echo $_catHasChildren; ?>"><?php echo $_catName ?></a>
                
                <?php
                // Start level 1 menu
                if ( $isCategory && $_category->hasChildren()  )
                { 
                ?>            
                    
                    <ul class="level<?php echo $level; ?>">
                        <?php
                        $subCats = $_category->getChildrenCategories();
                        $subCatIds = $subCats->toArray(array('entity_id'));
                        ?>
                        
                        <li class="level<?php echo $level; ?> view-all"><a class="level<?php echo $level; ?>" href="<?php echo $_category->getUrl(); ?>"><?php echo $this->__('See all'); ?> <?php echo $name; ?></a></li>
                        
                        <?php
                        foreach( $subCatIds as $subCatId )
                        {
                            $sub_cat = Mage::getModel('catalog/category')->load($subCatId);
                            if ( $sub_cat->getIsActive())
                            {
                                $catUrl = $sub_cat->getURL();
                                $catname = $sub_cat->getName();
                                ?>
                                
                                <li class="level<?php echo $level; ?><?php
                                    echo ' nav-' . $i . '-' . $i2;
                                    
                                    if ( $i2 == 0 )
                                    {
                                        echo ' first';
                                    }
                                    else if ( $i2 == (count($subCatIds) - 1) )
                                    {
                                        echo ' last';
                                    }
                                ?>">
                                    <a class="level<?php echo $level; ?>" href="<?php echo $catUrl; ?>">
                                        <?php echo $catname; ?>
                                    </a>
                                    
                                </li>
                                <?php 
                                $i2++;
                            }
                            
                        } ?>
                        <li class="level<?php echo $level; ?> back-link"><a class="level<?php echo $level; ?>" href="#"><?php echo $this->__('Back'); ?></a></li>
                        <?php $level = 0; ?>
                    </ul>
                    
                <?php }
                
                ?>
                
             </li>
             <?php $i++; ?>
         <?php }
         echo '</ol>';
     }
     echo '</nav>';
    
    ?>

Is it best practice tho?