ggppdk: I should have made clear, I'm using version 1.5.6 RC8 (r1465).
I cleared the sh404sef cache again and tried the default category template. Same result.
I'm doubting this is a template issue, per se. But, I don't understand how pagination works enough to see the problem clearly.
Here's the source code for the pagination area of a page with the issue. All I can see is that "Page-1" is being assigned to more than one "title." Same with "Page-2"
<!-- BOF pagination -->
<div class="pageslinks">
<ul class="pagination"><li>Start</li><li>Prev</li><li>1</li><li><strong>
2
</strong></li><li><strong>
3
</strong></li><li><strong>
4
</strong></li><li><strong>
5
</strong></li><li><strong>
6
</strong></li><li><strong>
7
</strong></li><li><strong>
8
</strong></li><li><strong>
9
</strong></li><li><strong>
10
</strong></li><li><strong>
Next
</strong></li><li><strong>
End
</strong></li></ul> </div>
<p class="pagescounter">
Page 1 of 145 </p>
<!-- EOF pagination -->
Francis