I discovered, in not a very amusing way that if you use
query_posts() then the variables for paginating with The Loop stop working.
Fixing this is easy, just add to
paged option on the array the variable
$paged, in this way:
query_posts( 'posts_per_page' => 15, 'paged' => $paged, );
Or if you don't use it like this, then:
query_posts('posts_per_page=15&paged=' . $paged);
After this, using
posts_nav_link() actually works.