Let me tell you why this is a major headache. When you use
wp_nav_menu() to create a navigation menu in a theme, it creates a nice menu using all the options you set with regards to classes, IDs, format - it allows you to style it nicely with CSS.
If for whatever reason there is no menu defined, WP attempts to create a menu based on a function in the
fallback_cb option, the default is
wp_page_menu() which generates completely different markup and classes, most of which cannot be edited at this point from the
wp_nav_menu(), thus rendering any styles for the proper menu redundant.
The only way around this is to effectively style your menu twice, or create a new fallback-callback which emulates
wp_nav_menu but with he default pages.