Paging in Category

Here is my problem…

When clicking on “Posted in Category”, it only shows the number of posts that is set by “Reading Options” , “Show at Most”…

I have over 1400 posts and most categorys have more than the number set by “Show at Most”. When clicking on the “Category” the number of posts displayed has no “Previous” or “Older” link on the page to show the rest of posts in that category. See this example

When using WP-PageNavi for categories it shows links to page 2 “http://domain/index.php/category/category name/page/2/”, but that returns an 404 error.

This occurs no matter what theme is being used.

When on the main index page WP-PageNavi works as designed and takes you to older posts.

Site Data:
WP 2.3.3
Theme: Classical Elegance

Suggetions?…