Custom Post Types strange pagination problem

by

I think your problem is at the following lines:

if ( get_query_var( 'post_type' ) )
    $post_type = get_query_var( 'post_type' );
else
    $post_type="job_listing";

Your post_type var will probably already being set, so you are calling some different post type (the one stored inside the query_vars array with the post_type key), which maybe does not have a second page and therefore leads you to your 404. You can simply 

var_dump( $GLOBALS['wp_query'] );

or 

printf( '<pre>%s</pre>', var_export( $GLOBALS['wp_query'], TRUE ) );`

depending on your debugging setup and take a look at the output to see what goes wrong in detail.

Aside from that, I’d

  1. Use get_posts() or new WP_Query() to not mess up the main query (query_posts() is a private function reserved for core usage).

  2. Set the query var fixed for that query:

    $post_type="job_listing";