wp_nav_menu not appearing for a couple pages

I had the same problem, but with a newer version of WordPress (3.7.1).

On pages with custom taxonomies of custom posts, the wp_nav_menu was not shown. The solution below worked for me.

in functions.php of the theme:

add_action( 'pre_get_posts', 'my_pre_get_posts' );
function my_pre_get_posts($query) {
  if ($query->get('post_type') === 'nav_menu_item') {
    $query->set('tax_query','');
  }
}