Menu Disappears on Category Pages

I have a site whose navigation disappears on category pages for posts in the ‘post’ post type, but not for posts in any of my custom post types. The ‘post’ post type and post of the custom post types use the same template file for theirs archives and headers – no differences. The menu is using the wp_nav_menu function. Example links below (again, same template files being used):

Menu: http://politichicks.tv/column/

No Menu: http://politichicks.tv/category/videos

I know this is an old question but seems that is still unresolved. As @Milo said you may have an incorrect pre_get_posts implementation.

Most people do this like this (example):

add_filter( 'pre_get_posts', 'query_post_type' );

function query_post_type( $query ) {
    if ( is_category() ) {
        $post_type = get_query_var( 'post_type' );
        if ( $post_type ) {
            $post_type = $post_type;
        } else {
            $post_type = array( 'nav_menu_item', 'post', 'departments' );
        }
        $query->set( 'post_type', $post_type );

        return $query;
    }
}

But we must change the line: $post_type = $post_type; and pass 'nav_menu_item' to the $post_type in order to menu to display, as follow:

add_filter( 'pre_get_posts', 'query_post_type' );
function query_post_type( $query ) {
    if ( is_category() ) {
        $post_type = get_query_var( 'post_type' );
        if ( $post_type ) {
            $post_type = array( 'nav_menu_item', $post_type );
        } else {
            $post_type = array( 'nav_menu_item', 'post', 'departments' );
        }
        $query->set( 'post_type', $post_type );

        return $query;
    }
}

I hope this help people who do this wrong and sorry for my bad English.