Previous/next link to post in category, NOT tag?

Defaults

First, you don’t have to put '« %link' in, as this is already the default value.

WPDB Query

Your “Problem” is, that the underlying funtion adjacent_post_link() uses get_adjacent_post() if it’s not querying an attachment.

This then builds the following JOIN part for the query:

INNER JOIN $wpdb->term_relationships 
    AS tr 
    ON p.ID = tr.object_id 
INNER JOIN $wpdb->term_taxonomy tt 
    ON tr.term_taxonomy_id = tt.term_taxonomy_id

Filter the query, before executing it:

Here’s the filter description from the core function:

apply_filters( "get_{$adjacent}_post_join", $join, $in_same_cat, $excluded_categories )

That means, that you can build the following plugin – IF you set the $in_same_cat argument to TRUE (Hint: This is the 3^rd argument for next_/previous_post_link()).

<?php
! defined( 'ABSPATH' ) AND exit;
/** Plugin Name: Intercept Next/Prev Posts links query <code>JOIN</code>. */

# Alter »PREVIOUS« query
function wpse64909_prev_link_query( $join, $in_same_cat, $excluded_cats )
{
    global $post;

    // Example: Only for specific post types.
    // $post_type = $post->post_type
    // if ( ! in_array( $post_type, array( 'post', 'page' ) )
    //     return;

    // alter $join - you have $in_same_cat and $excluded_cats to assist you

    return $join;
}
add_filter( 'get_previous_post_join', 'wpse64909_nextprev_link_query', 10, 3 );

# Alter »NEXT« query
function wpse64909_next_link_query( $join, $in_same_cat, $excluded_cats )
{
    global $post;

    // alter $join - you have $in_same_cat and $excluded_cats to assist you

    return $join;
}
add_filter( 'get_next_post_join', 'wpse64909_nextprev_link_query', 10, 3 );