I am having a somewhat similar issue. I can set the $in_same_cat to TRUE and the links completely disappear. Setting them to FALSE, they work properly but I am looking to only have prev/next go within the current category.
I am using a custom post type called "Portfolio" with a lot of categories. This is my current code for single_portfolio.php:
<?php if(get_the_term_list($post->ID, 'portfolio_category', '', '<br />', '')): ?>
<div id="single-nav-left"> <?php previous_post_link('%link', '« Previous', FALSE); ?> | </div>
<div id="single-nav-right"><?php next_post_link('%link', 'Next »', FALSE); ?></div>