Paging Returning 404 Error

I am going to try and break this down as detailed as possible. I am currently working on a client website that is being fully powered by WordPress. I have created custom pages and templates to display everything how I want it, and made a blog template to manually create my own queries.

Let me preface by saying, using “pretty” permalinks was causing all of the pages to return a 404, so i had to add index.php/ to the front of the custom permalink structure to get it to work. I don’t know if this is the cause of paging not working.

Back to the matter:
Everything runs fine on page 1 of the blog – the results show up as expected.
http://www.worldmission.cc/index.php/blog/

However, clicking to page 2 returns a 404 error saying the page is not found/has no results.
http://www.worldmission.cc/index.php/blog/page/2/

The code I am using to pull paging is below:

$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
   $postsperpage = 5;
   $args=array('posts_per_page'=>$postsperpage, 'paged'=>$paged, 'order'=>'DESC');
  $postss = query_posts($args);

Like I said, as you can see, page 1 loads fine, page 2 shows a 404 error. If I change the amount of posts per page to 7 for example, it returns more posts, but still page 2 errors out.

Here is where I get super confused. The top of my blog page has the following code:

<?php get_header(); ?>
  <div id="content">
  <div class="breadcrumb">
  <?php if(function_exists('bcn_display')) bcn_display(); ?>
  </div>
  <div id="contentleft">
  <h1>Blog</h1>
  <?php
   $paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
   $postsperpage = 5;
   $args=array('posts_per_page'=>$postsperpage, 'paged'=>$paged, 'order'=>'DESC');
   $postss = query_posts($args);
   if (have_posts()) : while (have_posts()) : the_post();  ?>

Now typically after this last line, the posts would start outputting on the page, however, when you get to page 2… for some reason, it’s sending me to the 404 page – almost as if its not getting past have_posts. So what I did was take this same exact code from above and add it to the top of the 404 page, then had it dump the value of $postss to the screen. Low and behold, all of the post information the page is SUPPOSED to outputting is just sitting in an array.

Can someone explain to me why wordpress is saying that it’s a 404… even though the posts are obviously there? And perhaps suggest a way to fix this?