Update (07 December 2011) : An update has been made to the plugin and is available for download from WordPress plugins directory. This will fix pagination on custom post types as well.
Plugin name : Category pagination fix
Release date : 2009-04-25
Fixes the bug in WordPress 2.7 ( may be in lower version also) in category listing page pagination. When you are using permalink structure as %category%/%postname% , second page URL of category listing page will be category-name/page/2 which WordPress identify “page” as post name. And will return 404 error page. This plug-in will fix the issue. This also fix the next and previous buttons bug in while using custom permalink structure.
I’m using this plug-in for this blog itself 🙂
1 . Unzip into your /wp-content/plugins/ directory.
2 . Activate the plugin through the ‘Plugins’ menu in WordPress
No issues reported yet. Please report issues in comments