Many people are experiencing issues with WordPress 3.4 and 404 errors. Some of these people have been able to fix the problem by resetting their permalinks, while others have had to disable plugins to get back to normal (for example, 404-error-on-2nd-page-of-blog-after-34-upgrade).
I believe that many of these problems are caused by plugins that circumvent
$wp_query. With recent changes to the
handle_404() function, if
$wp_query->posts is empty, the page will 404.
For example, I wrote a plugin that pulls data from a different data source instead of the posts table on my home page. When entering my blog on page 1, WordPress will find posts by luck; however, when navigating to page 2, various plugin functions which limit the main posts query will restrict it so that no posts are returns. I tested this by setting
$wp_query->posts = true in between
wp-includes/class-wp.php::main()-- **which is not advised at all**-- and it bypasses the issue, resulting in my hacky pages work properly.
This of course is not at all what you should do to fix the problem, but I think it points out an interesting issue: up until the 3.4 release,
handle_404() worked differently than it does now.
If you are a plugin developer, it's worth looking at these changes.
EDIT - Actually, the key is probably that
!is_home() no longer safeguards you from getting 404s. Either way, different 404 handling has resulted in different behavior than before.