Older Posts not showing up in TwenryTen theme

I’m having an issue and I know what the problem is but I’m just not certain where to add the code and in which template.

Basically, I have a permalink structure of /%category%/%postname%/ and as a result, any Older Posts link brings up a Not Found page. I had a similar issue with a Kubrick theme but this is TwenryTen and things are different. I need to know which PHP file in my template to tweak and what code. Seems it would be loop.php and this code….but how?

<?php if ( $wp_query->max_num_pages > 1 ) : ?>
	<div id="nav-above" class="navigation">
		<div class="nav-previous"><?php next_posts_link( __( '<span class="meta-nav">←</span> Older posts', 'twentyten' ) ); ?></div>
		<div class="nav-next"><?php previous_posts_link( __( 'Newer posts <span class="meta-nav">→</span>', 'twentyten' ) ); ?></div>
	</div><!-- #nav-above -->
<?php endif; ?>