When you add a new post, Wordpress APO refreshes the main index page and main category page, but not page 2 or any of the subsequent pages.
Since adding one new post will change not just the main listing page, but all the subsequent pages, it needs to invalidate these in the cache. So when you add a new post (or edit an existing post) it should update all index pages, all category pages for the selected categories (or categories removed in the case of an edit), and all tag pages for the tags added (or tags removed).
For now I have been frequently purging the cache as a work around, otherwise going to page 2 of the listings would be the page 2 from about 6 weeks ago when I added APO. (Which would look like my actual page 40 listings, since it is a busy site.)