I started using WordPress at about version 2.5 and when I customized my permalinks, I had a problem when there was more than one page. Only the first page of posts would display, and clicking Previous or Next to all other pages showed up as “404 sorry, nothing found!” The paging problem has something to with WordPress thinking that /page/ is a sub-category name as opposed to being a reference to a specific page.

So here is a very small plugin that attempts to fix the problem:

Click here to download the WP-PageNavigation Fix plugin.

I remember for sure that it worked in WP v2.7 and 2.8 but have not tested it on any other older versions, although it should probably work without a problem. The problem does not seem to be present in WP v3+ so I have not needed to use the plugin anymore since upgrading, but maybe somebody else has come across the problem.

Thanks to Doug Smith at http://barefootdevelopment.blogspot.com/2007/11/fix-for-wordpress-paging-problem.html