WordPress categories don’t refresh after calling wp_insert_term

I’ve been pulling my hair out for two weeks on this one, any help would be really appreciated.

I’m using WP multisite 3.2.

On the site front end I have a tool that uses wp_insert_term to add a new category to any one of the multisite blogs (Im using switch_to_blog() in case that matters).

I’m then calling wp_set_object_terms() to add a post to the new category created.

Both these work fine, the new category gets created and the post gets switched to that category.

The Problem:

The permalink for the post in the new category throws a 404 error.
The post does not get added to the Post Count for the new category.

Both these problems can be resolved by:

A) Go to wp-admin -> settings -> permalinks and save permalinks
B) Go to wp-admin -> posts -> categories -> and add any other category

The above two solutions won’t work for me as I can’t manually do this everytime a user uses the tool we built.

What we have tried:

function flush_permalinks() {
global $wp_rewrite;
$wp_rewrite->set_permalink_structure('/%postname%/');
}
add_action('init', 'flush_permalinks');

// This does not solve it

We have also tried:

function flush_permalinks() {
global $wp_rewrite;
$wp_rewrite->flush_rules();
}
add_action('init', 'flush_permalinks');

// This does not solve it

And we have tried:

add_action( 'init', 'create_initial_taxonomies', 0 ); 

//This does not solve it.

Thanks in advance for any help or pointing us in the right direction for a solution!