Wordpress has a nasty and annoyingly known bug that prevents paginated custom post type pages from abiding by a set posts_per_page value, this sets it straight. Replace the post type value of "project" with your own custom post type name, you can add OR c

gistfile1.php

/**
 * Wordpress has a known bug with the posts_per_page value and overriding it using
 * query_posts. The result is that although the number of allowed posts_per_page
 * is abided by on the first page, subsequent pages give a 404 error and act as if
 * there are no more custom post type posts to show and thus gives a 404 error.
 *
 * This fix is a nicer alternative to setting the blog pages show at most value in the
 * WP Admin reading options screen to a low value like 1.
 *
 */
function custom_posts_per_page( $query ) {

    if ( $query->is_archive('project') ) {
        set_query_var('posts_per_page', 1);
    }
}
add_action( 'pre_get_posts', 'custom_posts_per_page' );

Thanks. This saved the day. 3 days troubleshooting.

Nevermind, problem is still there.

This saved me as well. Since this didn't work for @orangeman555, in my case I needed to add $paged = ( get_query_var('paged') ) ? get_query_var('paged') : 1; before the query and 'paged' => $paged in the arguments of the query, then do a global $wp_query; $wp_query = new WP_Query( $args ); instead of creating a new query variable.

How the hell hasn't this been fixed in WP yet?