error 404 on next_posts_link

Hi,
I’ve been messing with wordpress lately – between many I’ve updated to 2.8.6 (from 2.8.4, cause 2.9 doesn’t work on my version of MySQL) and created new theme for my site.

Now, the issue is that the “older” posts link in categories doesn’t work for me.
To generate it I use

<div class="navigation">
		        <div class="nav_n"><?php previous_posts_link('newer') ?></div>
			<div class="nav_o"><?php next_posts_link('older') ?></div>
		</div>

^ that is in index.php of my theme, inside the <?php if (have_posts()) : ?> condition, under the <?php while (have_posts()) : the_post(); ?> loop displaying the list of posts.

The link generated by next_posts_link leads to: http://mysite.eu/index.php/mycategory/page/2
My permalink structure is: /index.php/%category%/%postname%

now, the curious thing is that when I change permalinks to… let’s say /index.php/%category%/%year%/%postname% than everything works! Even though the link to second page is just as it was before. But when I get back to /index.php/%category%/%postname% it doesn’t work anymore. -_- I don’t get it.

It also isn’t a matter of theme as pages don’t work with WordPress Default theme neither.

After some tests I’ve figured out that it’s not the matter of plugins (disabled all – still didn’t helped) but if I set the Front page displays to Your latest posts than pages works on the main page, but still doesn’t work for categories. Also it’s not the matter of Blog pages show at most setting – it didn’t work for any value in between 1 and 15 (it’s pointless to test more) – on default “5” setting it also doesn’t work.

Any ideas what can I do?
ps. I cannot change my permalinks structure (even if it fixes the bug).
pps. I don’t use .htaccess nor query_posts command