next_posts_link not working in index.php

I have a custom permalink structure of:

/%category%/%year%/%postname%/

For some reason under categories where this pagination is used (in index.php), I get strange errors.

<?php next_posts_link('<img src=\'/wp-content/themes/lightweight/images/b_next.gif\' border=\'0\' width=\'67\' height=\'20\' alt=\'Previous\' align=\'right\'/>', TRUE) ?><?php previous_posts_link('<img src=\'/wp-content/themes/lightweight/images/b_previous.gif\' border=\'0\' width=\'67\' height=\'20\' alt=\'Next\'/>', TRUE) ?>

The links return as:

http://www.new-media.ca/404.php/blog/page/2/?404;http://new-media_ca:80/blog

If I go directly to http://www.new-media.ca/blog/page/2/ it works.

Because I am on IIS, I have to use 404.php that looks like this:

<?php
$qs = $_SERVER['QUERY_STRING'];
$_SERVER['REQUEST_URI'] = substr($qs, strpos($qs, ':80')+3);
$_SERVER['PATH_INFO'] = $_SERVER['REQUEST_URI'];
include('index.php');
?>

I am not sure why this started happening since the upgrade to 2.8. The strange thing is that pagination on posts works just fine – http://www.new-media.ca/blog/2009/ontario-buy-local-grocers-go-independent/

Any ideas? I really appreciate your help. I am also running to remove “/category/” from the URLs, but I know that it’s not the source of the problem (I’ve disabled it and still got the same strings with /category/ base).