I recently experienced the same problem and I decided to have a look inside WP and fix it by myself.
That's a bug in the link-template.php file. Basically, just a missing dot and a mismatch of variables.
You can easily patch it yourself : in the file wordpress/wp-includes/link-template.php, locate "function get_previous_post" (and its counterpart, "function get_next_post").
Now, in both functions, replace the following part of the code... (Note that this code may slightly differ from one version of WP to another.)
$sql_exclude_cats = '';
if ( !empty($excluded_categories) ) {
$blah = explode(' and ', $excluded_categories);
foreach ( $blah as $category ) {
$category = intval($category);
$sql_cat_ids = " OR pc.category_ID = '$category'";
}
$posts_in_ex_cats = $wpdb->get_col("SELECT p.ID from $wpdb->posts p LEFT JOIN $wpdb->post2cat pc ON pc.post_id = p.ID WHERE 1 = 0 $sql_cat_ids GROUP BY p.ID");
$posts_in_ex_cats_sql = 'AND ID NOT IN (' . implode($posts_in_ex_cats, ',') . ')';
}
... with these lines :
$sql_exclude_cats = '';
if ( !empty($excluded_categories) ) {
$blah = explode(' and ', $excluded_categories);
foreach ( $blah as $category ) {
$category = intval($category);
$sql_exclude_cats .= " OR pc.category_ID = '$category'";
}
$posts_in_ex_cats = $wpdb->get_col("SELECT p.ID FROM $wpdb->posts p LEFT JOIN $wpdb->post2cat pc ON pc.post_id=p.ID WHERE 1 = 0 $sql_exclude_cats GROUP BY p.ID");
$posts_in_ex_cats_sql = 'AND ID NOT IN (' . implode($posts_in_ex_cats, ',') . ')';
}
Hope that it will be useful and that this bug will be fixed in the next release of WP.