Posts repeat on page 2

My problem is this:

Now that I have more than 10 posts, there is a “next” link, which should allow users to go back and see older posts than the 10 most recent ones. “Next” does in fact link to the right page – http://mydomain.com/page/2 – however this page just displays those 10 most recent posts, not the older ones.

The interesting thing is that in the archives, this feature works fine, i.e. if you select the April archive you get the 10 most recent posts, then at the bottom a “next” link that takes you to http://mydomain.com/2009/04/page/2/ and this page displays the older posts properly.

Here is the code from my index.php file:

<?php include_once('header-index.php'); ?>

<div id="midle" class="fl mgright">
<div class="spacer">

 	<?php if (have_posts()) : ?>
	 <?php query_posts('cat=all'); ?>
		<?php while (have_posts()) : the_post(); ?>

<div class="post" id="post-<?php the_ID(); ?>">
<h2><a href="<?php the_permalink() ?>" title="<?php the_title_attribute(); ?>"><?php the_title(); ?></a></h2>
<div class="postdata">
   <ul>
    <li class="time"><?php the_time('F jS, Y') ?></li>
	<li class="posted">Posted in <?php the_category(', ') ?></li>
	<li><?php edit_post_link('Edit', '', ''); ?></li>
   </ul>
  </div>
<?php the_content('<img src="' . get_bloginfo('template_url') . '/img/rmore.gif" alt="'. get_the_title() .'" />', '', '');?>
<div class="clr"></div>
</div>

 <?php endwhile; ?>

 		<div id="navigation">
			<div class="alignleft"><?php previous_posts_link('<img src="' . get_bloginfo('template_url') . '/img/prev.gif" alt="previous post" />', '', '') ?></div>
			<div class="alignright"><?php next_posts_link('<img src="' . get_bloginfo('template_url') . '/img/next.gif" alt="next post" />', '', '') ?></div>
			<div class="clr"></div>
		</div>

	<?php else : ?>
	<div class="post">
		<h2 class="center">Not Found</h2>
		<p class="center">Sorry, but you are looking for something that isn't here.</p>
	</div>

	<?php endif; ?>

</div>
</div>

<?php get_sidebar(); ?>

<?php get_footer(); ?>

If the problem is probably somewhere else, let me know and I can post that code too. I really appreciate any help you can give. Thanks.