You can use output buffering to work around this issue.
Sandwich the category.php file that calls the pagination with it like so:
<?php ob_start('fixCategory'); ?>
<?php previous_posts_link(); echo ' '; next_posts_link() ?>
<?php ob_end_flush(); ?>
Then create a function in your functions.php theme file that fixes poorly routed links:
function fixCategory($str){
$base = get_bloginfo('url');
return str_replace("{$base}/news/", "{$base}/category/news/", $str);
}
Please note that this example function only fixes one category: “news”. You can use PHP’s preg and str replace functions to develop a smarter function to handle multiple categories.
