pagination for custom loops – page not found 404

I am creating a custom search and all is working just having issues when there are more than 10 posts and you click the next button and it goes to a 404 not found.

The search functionality in on a custom taxonomy called recipes.

Here the site that is currently running. If you select ONLY summer you will see the posts come up and the button.

Here the code I have used for that page.

if( isset($_GET['s']))
{
    //now we need to check whether each taxonomy section is set or not.
    //the start of the array
    $tax_query = array('relation' => 'AND',);

    //All the Different taxonomies we need to check!
    $taxonomies = array('epx_recipes_season','epx_recipes_course','epx_recipes_requirements','epx_recipes_cuisines','epx_recipes_occasions','epx_recipes_typeofcooking');

    //Now need to check each taxonomy
    foreach($taxonomies as $tax){
        //check if something from that taxonomy has been sent
        if (isset($_GET[$tax])) {
            //run through how many have been sent
            foreach ( $_GET[$tax] as $option ) {
                //Now make a array with the different part init
                $arg = array(
                    'taxonomy' => $tax,
                    'field' => 'slug',
                    'terms' => $option
                );
                //Now add it to the main array
                $tax_query[] = $arg;
            }
        }
    }

    //Now all this has been run through need to send the query
    //first get the paged information
    $custom_query_args['paged'] = get_query_var( 'paged' ) ? get_query_var( 'paged' ) : 1;
    //now set the query that required
    $args = array( 'post_type' => 'recipes',
            'orderby'=> 'title',
            'order' => 'asc',
            'post_status' => 'publish',
            'posts_per_page' => '10',
            's'    => $s,
            'paged'=> get_query_var( 'paged' ),
            'tax_query' => $tax_query
        );
}
else{
    //Nothing has been searched, send normal query
    $args = array( 'post_type' => 'recipes',
            'orderby'=> 'title',
            'order' => 'asc',
            'post_status' => 'publish',
            's'    => $s,
            'paged'=>get_query_var( 'paged' ),
        );
}

and the code to show the recipes is

<?php
                //run the custom query
                $my_query = new WP_Query( $args );
                $temp_query = $wp_query;
                $wp_query   = NULL;
                $wp_query   = $my_query;
                if ($my_query->have_posts()) : ?>

                <?php while ($my_query->have_posts()) : $my_query->the_post(); ?>
                                    <?php
                    //get the Featured Image
                    $image_url = wp_get_attachment_image_src(get_post_thumbnail_id(),'large-thumb', true);
                ?>                   

                <article class="the-recipe">
                    <div class="featuredimage">
                        <a href="<?php the_permalink() ?>">
                        <?php
                                //output featured image
                                $output ="";
                                $output .= '<img src="'.$image_url[0].'" alt="'.get_the_title().'">';
                                echo $output;
                            ?>
                        </a>
                    </div>
                    <div class="the-recipe-title">
                        <h2>
                            <a href="<?php the_permalink() ?>" rel="bookmark" title="Permanent Link to <?php the_title_attribute(); ?>"><?php the_title(); ?></a>
                        </h2>
                    </div>

                    <div class="the-recipe-entry">
                        <?php the_excerpt(); ?>
                        <a class="the-recipe-more" href="<?php the_permalink() ?>">View this recipe</a>
                    </div>

                </article>
                <?php endwhile; ?>

                <div class="the-recipe-navigation">
                    <span class="previous-entries"><?php next_posts_link( 'Newer Posts', $custom_query->max_num_pages ); ?></span>
                    <span class="next-entries"><?php previous_posts_link( 'Older Posts' ); ?></span>
                </div>

            <?php else : ?>
                <h2>Not Found</h2>
                <p>Sorry, there are not Recipes in what you searched :(</p>
            <?php endif;
                // Reset main query object
                $wp_query = NULL;
                $wp_query = $temp_query;

?>

However I have looked around but I can think how to get this work. I have tried a few thing but it tends to restart the query and forget the query.