Until now, if you use next_post_link(‘%link’, ‘%title’, true) or previous_post_link(‘%link’, ‘%title’, true) to get the adjacent post for a custom post type which has a taxonomy assigned to it, it doesn’t work as intended. This is because these two functions are based on get_adjacent_post() which is hardcoded to look to the taxonomy ‘category’. So hard luck if you need them to work for your custom taxonomy.

There is a plugin that helps solve this issue: http://wordpress.org/extend/plugins/previous-and-next-post-in-same-taxonomy (update: this plugin is no longer available).  And work is ongoing to resolve this, which you might want to have a read: http://core.trac.wordpress.org/ticket/17807 .

However, if you have customised the order of your custom post type posts, the above plugin is not going to work, because the above mentioned functions are hardcoded to get next and previous posts based on their post dates.

So if you need to get next and previous post links in the same custom taxonomy, with a custom posts order, you might want to try these few lines of codes in your single.php template:

// get_posts in same custom taxonomy
$postlist_args = array(
   'posts_per_page'  => -1,
   'orderby'         => 'menu_order title',
   'order'           => 'ASC',
   'post_type'       => 'your_custom_post_type',
   'your_custom_taxonomy' => 'your_custom_taxonomy_term'
); 
$postlist = get_posts( $postlist_args );

// get ids of posts retrieved from get_posts
$ids = array();
foreach ($postlist as $thepost) {
   $ids[] = $thepost->ID;
}

// get and echo previous and next post in the same taxonomy        
$thisindex = array_search($post->ID, $ids);
$previd = $ids[$thisindex-1];
$nextid = $ids[$thisindex+1];
if ( !empty($previd) ) {
   echo '<a rel="prev" href="' . get_permalink($previd). '">previous</a>';
}
if ( !empty($nextid) ) {
   echo '<a rel="next" href="' . get_permalink($nextid). '">next</a>';
}

Hope this helps!

Update:

The above issues to get adjacent posts based on taxonomy has been fixed according to http://core.trac.wordpress.org/ticket/17807 , but this is still limited to getting posts sorted by post date only. However, this is being resolved here: https://core.trac.wordpress.org/ticket/26937 .

You can now add a $taxonomy argument to each of the adjacent post functions. Previously, related functions took an array of category (IDs) to search. These can now be taxonomy term IDs and each function now has $taxonomy = ‘category’ as an optional argument.

Related functions affected: get_previous_post(), get_next_post(), get_adjacent_post(), get_adjacent_post_rel_link(), adjacent_posts_rel_link(), next_post_rel_link(), prev_post_rel_link(), get_boundary_post(), get_previous_post_link(), previous_post_link(), get_next_post_link(), next_post_link(), get_adjacent_post_link(), adjacent_post_link().