posts_nav_link not working with date and name-based permalinks

When I was wanted to show a specific number of posts in a category, I was able to make posts_nav_link work using this code:

<?php query_posts($query_string . '&showposts=3'); ?>

However, once I turned my permalinks to date and name-based, the ‘Next’ link broke after clicking it an additional time.

I am also using a category template (category-4.php) if that might be the cause.

Here is my code:

<h2 class="cat"><?php echo single_cat_title(); ?></h2>

<?php query_posts($query_string . '&showposts=3'); ?>
<?php if (have_posts()) : ?>
<?php while (have_posts()) : the_post(); ?>

<div class="entry">
<h3 class="entrytitle" id="post-<?php the_ID(); ?>"> <a href="<?php the_permalink() ?>" rel="bookmark">
<?php the_title(); ?></a></h3>

<?php the_meta(); ?>

<div class="entrybody">
<?php the_excerpt();?>
</div>

<div class="entrymeta">
<?php the_time('F j, Y '); ?> &bull; <?php the_category(); ?> &bull;
<?php $comments_img_link= '<img src="' . get_stylesheet_directory_uri() . '/images/comments.gif"  title="comments" alt="*" />';
comments_popup_link($comments_img_link .' Comments(0)', $comments_img_link .' Comments(1)', $comments_img_link . ' Comments(%)'); ?>
<?php edit_post_link(__(' Edit')); ?>
</div>

<!--
<?php trackback_rdf(); ?>
-->
</div>
<?php comments_template(); // Get wp-comments.php template ?>
<?php endwhile; else: ?>
<p>
<?php _e('Sorry, no posts matched your criteria.'); ?>
</p>
<?php endif; ?>
<p>
<?php posts_nav_link(' — ', __('&laquo; Previous Page'), __('Next Page &raquo;')); ?>
</p>
</div>

Any suggestions?