get_previous_post in same categories

get_previous_post uses get_adjacent_post() which has a bunch of filter hooks you can use but a much simpler approach would be to create your own function, something like this:

// Create a new filtering function that will add our where clause to the query
function date_filter_where( $where="" ) {
    global $post;
    $where .= " AND post_date >= '".$post->post_date."'";
    return $where;
}

//then create your own get previous post function which will take an array of categories eg: 
// $cats = array('1','2');
function my_get_previous_post($cats){
    global $post;
    $temp = $post;
    $args = array(
        'posts_per_page' => 1,
        'post_type' => 'post',
        'post_status' => 'publish',
        'category__and' => $cats
    );
    add_filter( 'posts_where','date_filter_where' );
    $q = new WP_Query($args);
    remove_filter( 'posts_where','date_filter_where' );
    while ($q->have_posts()){
        $q->the_post;
        echo '<a href="'.get_permalink($post->ID).'">'.get_the_title($post->ID).'</a>';
    }
    $post = $temp;
    wp_reset_query();
}