bug in pagination with nextpage when using category in permalink

@fozloki – we’re discussing about this problem over here too!

This is a known bug with WordPress 3.0, and there is a bug fix logged in the Trac database, found here:
http://core.trac.ww.wp.xz.cn/ticket/13471

As a temporary and immediate fix on my site, we made a very small change to the post-template.php file in the wp-includes directory.

You need to replace line 622, which currently looks like this:
$output .= '<a href="' . trailingslashit(get_permalink()) . user_trailingslashit($i, 'single_paged') . '">';

With:
$output .= '</a><a href="' . trailingslashit(get_permalink()) . user_trailingslashit('?page=' . $i, 'single_paged') . '">';

THEN, also replace line 636 in exactly the same way, replacing:
$output .= '</a><a href="' . trailingslashit(get_permalink()) . user_trailingslashit($i, 'single_paged') . '">';

With:
$output .= '</a><a href="' . trailingslashit(get_permalink()) . user_trailingslashit('?page=' . $i, 'single_paged') . '">';

It should work fine after this fix.