I have the standard permalink structure and have replaced %postname% with %post_id%: as follows /index.php/%year%/%monthnum%/%day%/%post_id%/. I'm able to access all of my pages with this structure.
When I look at my home page which breaks at 10 posts - I can click on the next link and it takes me to /index.php/page/2/ - everything seems to work.
When I look at a category page with more than 10 posts and click on the next link it also takes me to /index.php/page/2/ instead of /index.php/category/category-name/page/2/.
I'm using IIS 6 on a W2003 server.
It looks like posts_nav_link doesn't pick up permalink structure. By the way when I remove the permalink structure everything works ok.