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