I've done this before on two or three other sites in WP V 3.2.1 using this;
<?php previous_post_link( '%link', '<span class="meta-nav">' . _x( '←', 'Previous post link', 'twentyten' ) . '</span> %title', TRUE ); ?></div> <div class="nav-next"><?php next_post_link( '%link', '%title <span class="meta-nav">' . _x( '→', 'Next post link', 'twentyten' ) . '</span>', TRUE ); ?></div>
Here is the proof: http://www.southeasterncompanies.com/category/our-team/ (click on a single employee and on the 'single-our-team.php' the prev / next links only go to posts within the 'our team' category).
I tried this very same code (the very same set up) in a modified 2010 for WP v 3.3.1 and it didn't work. NextI even uploaded the theme from the above site to this install of WP 3.3.1 and it didn't work.
So then I double checked my posts to make sure they were assigned to just one category, and the correct category. Then I checked my categories. I found nothing obvious there.
So then I dug around and found this, used it, and it didn't work at all (nothing showed up on the screen).
<div class="nav-previous"><?php previous_post_link($format, $link, $in_same_cat = true, $excluded_categories = ''); ?></div> <div class="nav-next"><?php next_post_link($format, $link, $in_same_cat = true, $excluded_categories = ''); ?></div>
I'm still getting navigation to posts that are not in the same category.
I also checked to make sure that the correct single template is being used (single-news.php - I typed WTF?!?! a div on that file... so I know I'm uploading the change and it is using the correct template file).
FWIW - Both sites are hosting at Host Gator, and here is the whole bloody single-news.php source code http://pastebin.com/wHcQuRmF with a screen shot of the posts list in WP http://www.ratest6.com/TroubleShoot.png