Thanks for the reply moshu. I have upgraded to the latest version of WP (2.0.2) but the issue was present in 1.5 too. The code in both the index and archive templates is:
<div class="navigation">
<div class="alignleft"><?php next_posts_link('« Previous Entries') ?></div>
<div class="alignright"><?php previous_posts_link('Next Entries »') ?></div>
</div>
I’m taking a look at the get_pagenum_link() function at the moment to see if I can figure out why it’s not detecting my rewrite rules.