Next/Previous links doesn’t work in the same category

This is the default in WordPress Twenty Eleven Theme

<nav id="nav-single">
        <h3 class="assistive-text"><?php _e( 'Post navigation', 'twentyeleven' ); ?></h3>
        <span class="nav-previous"><?php previous_post_link( '%link', __( '<span class="meta-nav">&larr;</span> Previous', 'twentyeleven' ) ); ?></span>
        <span class="nav-next"><?php next_post_link( '%link', __( 'Next <span class="meta-nav">&rarr;</span>', 'twentyeleven' ) ); ?></span>
</nav><!-- #nav-single -->

I copy pasted your code to replace the above default code.

<nav id="nav-single">
    <span class="nav-previous"><?php previous_post_link('%link', __('<span class="meta-nav">&larr;</span> Previous'), TRUE); ?></span>
    <span class="nav-next"><?php next_post_link('%link', __('Next <span class="meta-nav">&rarr;</span>'), TRUE); ?></span>
</nav><!-- #nav-single -->

Your code is working perfectly on my system. Your code doesn’t have any problem. You can refer to Codex for changing your code further.

http://codex.wordpress.org/Function_Reference/previous_post_link