Wordpress 3.1.2 Permalinks Broken

I have a fresh install of WordPress 3.1.2 (not upgraded but installed fresh), containing no plugins whatsoever.

I'm having what seems to be from my googling a fairly common problem, but none of the solutions I can find work for me.

I have a custom taxonomy and a custom post type running, the code from my functions.php:

register_post_type( 'product', array(
    'labels' => array(
        'name' => __( 'Products' ),
        'singular_name' => __( 'Product'),
        'add_new_item' => __( 'Add New Product'),
        'add_new' => __( 'Add a Product'),
        'edit_item' => __( 'Edit Product'),
        'new_item' => __( 'New Product'),
        'view_item' => __( 'View Product'),
        'search_items' => __( 'Search products' ),
        'not_found' => __( 'No products found' ),
        'not_found_in_trash' => __( 'No products found in Trash' )
    ),
    'public' => true,
    'supports' => array(
        'title',
        'editor'
    ),
    'has_archive' => true,
    'can_export' => true
));

register_taxonomy( 'product_category', 'product', array(
    'hierarchical' => true,
    'labels' => array(
        'name' => 'Product Categories',
        'singular_name' => 'Product Category',
        'search_items' =>  __( 'Search Product Categories' ),
        'all_items' => __( 'All Product Categories' ),
        'parent_item' => __( 'Parent Product Category' ),
        'parent_item_colon' => __( 'Parent Product Category:' ),
        'edit_item' => __( 'Edit Product Category' ), 
        'update_item' => __( 'Update Product Category' ),
        'add_new_item' => __( 'Add New Product Category' ),
        'new_item_name' => __( 'New Product Category Name' ),
        'menu_name' => __( 'Product Categories' ),
    ),
    'public' => true,
    'rewrite' => array(
        'hierarchical' => true
    )
));

The problem is that when I go to a product_category archive page, for example http://example.com/dairy-industry, I get a 404. I have tried about a gajillion fixes, including

every combination of rewrite arguments on the register_taxonomy code
re-saving permalinks
turning permalinks off, saving, then turning them on again
the above, but first deleting the .htaccess file from the server
the above, but first deleting the rewrite_rules option from the wp_options table
having the category base and tag base option set (and blank)

I also do not have $wp_rewrite->flush_rules() anywhere in my theme.

The most frustrating thing is that at various times throughout my fixes, and with no pattern I can identify, the custom taxonomy archive pages will start working again, but the regular pages will start giving me 404s instead. They never work at the same time, and I can't figure out which steps will reproducibly make one or the other work. It seems to be totally random.

For a further bit of interestingness, when the custom taxonomy archive pages are not working, one of them (dairy-industry) redirects to the slug of a similarly-named but different (2011/04/dairy-industry-products) post before giving me a 404.

I'm happy to share any code that may be helpful, just ask.

Can anyone help me figure out this perplexing conundrum?

Solution

For me helped this answer: word-press-permalinks-broken-fro-category-and-tags-404-error-page-not-found

Simply Check your plugins and if you have “Simple Tags” or “Multipage Toolkit“ edit plugins, and replace:

$wp_rewrite->flush_rules();

with:

/* $wp_rewrite->flush_rules(); */

After, go to your permlinks page and update them... twice. Worked as a charm.