get_adjacent_post is the function WP now uses to have
previous_post_link and such functions working.
Anyway the ability to exclude a category when spewing the link is broken for me.
To reproduce this problem just try having
previous_post_link exclude one of the categories, like such:
previous_post_link($format='« %link', $link='%title', $in_same_cat = false, $excluded_categories = '2')
(or whatever category you want to exclude: it will be simply ignored.)
The culprit is
get_adjacent_post, but i find it totally complicated now so I just couldn't fix it.