I am using "%category%/%postname%.html" as my permalink structure. However, the "previous entries" and "next entries" links use index.php in their URLs, not the category/date URLs with /page/ appended. (eg. http://crazedmonkey.com/blog/2005, providing that the DNS is pointing to the right server.)
My archive.php contains the following:
<span class="prev"><?php next_posts_link('« Previous Entries') ?></span>
<span class="next"><?php previous_posts_link('Next Entries »') ?></span>
The weird thing is, this produces pretty URLs on my local server but not on the hosted server, even though I simply copied the WordPress install (2.0.4) and database. The hosted server is running PHP5 while my local is running PHP4.4.1.