Fallback_cb is messing around with containers

basically you are missing the container div so if you change your fallback to a custom function you can pass parameters to wp_page_menu that give you a bit of control over it and add your missing div try:

$wp_nav_header = array( 
    'container' => '',
    'menu_class' => 'sf-menu',
    'fallback_cb' => 'my_fallback_menu',
    'theme_location' => 'primaryheader',
    'depth' => 0,);
wp_nav_menu( $wp_nav_header);


function my_fallback_menu(){
    echo '<div class="sf-menu">';
    $args = array(
        'sort_column' => 'menu_order, post_title',
        'menu_class'  => '',
        'include'     => '',
        'exclude'     => '',
        'echo'        => true,
        'show_home'   => false,
        'link_before' => '',
        'link_after'  => '' );
    wp_page_menu($args);
    echo '</div>';
}

Hope this helps