WordPress paginate_links() function, 404s and trouble

This has been a horrendous, crippling, time stealing (two week) horrible horrible problem.

It might be rewriting, my use of custom posts, but after stripping out so much (and reducing some functionality of my theme) I’ve reduced my problem to this:

paginate_links() is putting out a link like this:

?s=cute&post_type=image&paged=2

When I changed the variable in the browser bar to page=2 (dropping the ‘d’).

?s=cute&post_type=image&page=2 

It works correctly.

So my question reduced to this: If I must get that function to output the “page” variable properly, how is that done?

paged and paged are both used by WordPress. So conversely, how do I get paged recognized if that is better practice?

For all I know, this is indicative of some deeper issue I have in my theme, but for the life of me I can’t see how else I could be going wrong!

EDIT:

Here is my code I’m using:

if ( get_query_var('paged') )

        $paged = get_query_var('paged');

    elseif ( get_query_var('page') )

        $paged = get_query_var('page');

    else
        $paged = 1;     

    $big = 999999999; // need an unlikely integer

    $stuff_to_echo =  paginate_links( array(
        'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
        'format' => '?page=%#%',
        'current' => max( 1, $paged ),
        'total' => $wp_query->max_num_pages,
        'type' => 'array'
    ) );

EDIT 2 – If above is good, here is another possible area the problem might be happening. I’ll post the creation of the custom post type and the rewrite rules –

//image custom post type

add_action( 'init', 'symbiostock_image_manager_register' );

function symbiostock_image_manager_register( )
{
    //creating custom post type for image

    $labels = array(
         'name' => 'Symbiostock Images',
        'singular_name' => 'Image',
        'add_new' => 'New Image',
        'add_new_item' => 'Add New Image',
        'edit_item' => 'Edit Image',
        'new_item' => 'New Image',
        'all_items' => 'All Images',
        'view_item' => 'View Image',
        'search_items' => 'Search Images',
        'not_found' => 'No image found',
        'not_found_in_trash' => 'No images found in Trash',
        'parent_item_colon' => '',
        'menu_name' => 'RF Images' 
    );

    $args = array(

         'labels' => $labels,
        'singular_label' => __( 'Image' ),
        'description' => 'Image Listings',
        'menu_position' => 100,
        'menu_icon' => symbiostock_IMGDIR . '/symbiostock_icon2.png',
        'public' => true,
        'publicly_queryable' => true,
        'show_ui' => true,
        'capability_type' => 'post',
        'hierarchical' => true,
        'has_archive' => true,
        'exclude_from_search' => false,
        'supports' => array(
             'title',
            'editor',
            'thumbnail' 
        ),
        'rewrite' => array(
             'slug' => 'image',
            'with_front' => false 
        ) 

    );


    register_post_type( 'image', $args );

    register_taxonomy( 'image-type', array(
         'image' 
    ), array(
         'hierarchical' => true,
        'label' => 'Image Categories',
        'singular_label' => 'Image Type',
        'rewrite' => true,
        'exclude_from_search' =>false,
        'public' => true, 
        'slug' => 'image-type' 
    ) );

    register_taxonomy( 'image-tags', array(
         'image' 
    ), array(
         'hierarchical' => false,
         'rewrite' => true,
         'query_var' => true,
        'singular_label' => 'Image Keyword',

        'hierarchical'            => false,
        'labels'                  => $labels,
        'show_ui'                 => true,
        'show_admin_column'       => true,
        'update_count_callback'   => '_update_post_term_count',


        'slug' => 'image-tag',               
        'labels' => array(
            'name' => _x( 'Image Keywords', 'taxonomy general name' ),
            'singular_name' => _x( 'Keywords', 'taxonomy singular name' ),
            'search_items' =>  __( 'Search Images' ),
            'all_items' => __( 'All Image Keywords' ),
            'edit_item' => __( 'Edit Image Keyword' ),
            'update_item' => __( 'Update Image Keyword' ),
            'add_new_item' => __( 'Add New Image Keyword' ),
            'new_item_name' => __( 'New Keyword Name' ),
            'menu_name' => __( 'Image Keywords' ),
            ),
        'rewrite' => array(
            'slug' => 'search-images', // This controls the base slug that will display before each term
            'with_front' => false, 
            'hierarchical' => false 
        ),
    ) );

}

add_action( 'admin_init', 'symbiostock_image_directory' );

function symbiostock_image_directory( )
{
    add_meta_box( 'symbiostock-image-meta', 'Symbiostock Image Info', 'symbiostock_image_manager_meta_options', 'image', 'normal', 'high' );

}

And here are the rewrite rules further down –

add_action( 'init', 'symbiostock_rewrite' );

function symbiostock_rewrite( )
{   

    global $wp_rewrite;
    $wp_rewrite->add_permastruct('typename','typename/%year%%postname%/' , true , 1);
    add_rewrite_rule('typename/([0-9]{4})/(.+)/?$','index.php?typename=$matches[2]', 'top');
    $wp_rewrite->flush_rules();

}