Index.php pagination broken/disappeared on Multisite

I’m running a multisite version of WordPress with about 70 sites on it for different blogs for our news organization, The Denver Post. About a month ago, our pagination links at the bottom of the index.php page stopped appearing. However, if you type in the URL for the next page of posts (i.e., /page/2/ … or /page/3/), you get the output for the newer entries, but not older posts (scroll to the bottom and you’ll see ‘Read Newer Entries.’). This continues no matter what page you go to.

Each site has the same url structure — blogs.denverpost.com/[blogname] — with the except of two, which are at their own domain names. We use a plugin to resolve this issue.

Here’s the code for what’s not working on index.php

<div class="postnavigation">
<div class="rightdouble">
<?php previous_posts_link('Read Newer Entries ?', 0) ?>
</div>
<div class="leftdouble">
<?php next_posts_link('? Read Previous Entries', 0); ?>
</div>

We’ve attempted to upgrade our version of WordPress to 3.2.1 in a testing environment, but that doesn’t solve the problem. We also upgraded and disabled all plugins in the testing environment (on the same server), and that didn’t fix the issue, either.

Is this a server configuration issue? Any help would be appreciated. Thank you!