Next and previous post issue

I tried to set up next/previous post links on my single.php page to limit to the current category. Other than the functions being poorly named (they should have been “earlier” and “later” to make more sense), I had no problems setting everything up. The look like

next_post_link(‘« %link’, ‘%title’, true)
previous_post_link(‘%link »’, ‘%title’, true)

However, it is definitely not working correctly.

If I go into a post in the “middle” of a category (i.e.-pull up a category page and click on a post in the middle of the page) everything works great. The links page back and forth between the posts in that category.

The problem lies in when I reach the end or beginning of a category, or when a category is small (1 or 2 posts). Then, the links point to posts in a completely different category. So, when I get to the “end” or “beginning” of a category, and only one link appears, instead of the link pointing back to where I came from it points to some random post in another category. It is so random I haven’t been able to detect a pattern.

I only use one category on a post, so that doesn’t seem to be the issue. I have no other navigation plugins active.

Any suggestions are appreciated.