Previous/Next custom post links within custom taxonomy

I managed to solve this, with some steering in the right direction in the comments under my question, by specifying different templates for different taxonomy terms using single-show.php to divert as follows:

if ( have_posts() ) { the_post(); rewind_posts(); }
    if (has_term('current', 'show_status')) {
        include(TEMPLATEPATH . '/single-show-current.php');
    }
    elseif (has_term('past', 'show_status')) {
        include(TEMPLATEPATH . '/single-show-past.php');
    }
    else {
        include(TEMPLATEPATH . '/single-default.php');
    }

Then, in the single-show-current.php and single-show-past.php templates I specified navigation based on term rather than taxonomy, as pointed out by Max, above (thank you for the help getting here).

The solution is based on this code at Bucket Press.

$postlist_args = array(
    'posts_per_page'  => -1,
    'orderby'         => 'menu_order title',
    'order'           => 'ASC',
    'post_type'       => 'show',
    'show_status'    => 'current'
    ); 
    $postlist = get_posts( $postlist_args );
    $ids = array();
    foreach ($postlist as $thepost) {
        $ids[] = $thepost->ID;
    }   
    $thisindex = array_search($post->ID, $ids);
    $previd = $ids[$thisindex-1];
    $nextid = $ids[$thisindex+1];
    if ( !empty($previd) ) {
        echo '<div class="olderlink"><p><a rel="prev" href="' . get_permalink($previd). '">&lsaquo; Previous</a></p></div>';
                        }
    if ( !empty($nextid) ) {
        echo '<div class="newerlink"><p><a rel="next" href="' . get_permalink($nextid). '">Next &rsaquo;</a></p></div>';
    }

Finally, to make this user-proof I installed the radio buttons for taxonomies plugin and applied it to this post type, effectively reducing the number of possible assignations to 1.