You should be able to exclude the category you don’t want to show by adding $excluded_terms to your navigation links. So for example, if the category you don’t want showing up is id 4 your link would look like:
<?php next_post_link( '%link', 'Next Post', false, '4' );?>
Same with previous_post_link()
.