How to add custom permalink structures?

Up until WordPress 3, we have been running some code in one of our plugins which changes how WordPress reads tag URL’s. Instead of the standard /tags/oranges/ type structure, we’ve been using something along the lines of /s/37/tags/oranges/ which allowed us to split the site into multiple sections. (for example, the above might show different posts than say /s/25/tags/oranges/)

The code we were using seemed to be working fine up until WordPress 3.0. I have included it below. It is an adapted form of the example found near the bottom of this page of Ryan Boren’s Feed Director plugin:
http://codex.wordpress.org/Function_Reference/WP_Rewrite

The code we’ve been using:

add_action('generate_rewrite_rules', 'sectioncats_add_rewrite_rules');
function sectioncats_add_rewrite_rules( $wp_rewrite )
{
	$new_rules = array(
		'[Ss]/([0-9]+)/tags/([^/]+)/?$' => 'index.php?' .
			'tag=' . $wp_rewrite->preg_index(2) .
			'&section_id=' . $wp_rewrite->preg_index(1),

		'[Ss]/([0-9]+)/tags/([^/]+)/page/?([0-9]{1,})/?$' => 'index.php?' .
			'tag=' . $wp_rewrite->preg_index(2) .
			'&paged=' . $wp_rewrite->preg_index(3) .
			'&section_id=' . $wp_rewrite->preg_index(1),
	);

	$wp_rewrite->rules = $new_rules + $wp_rewrite->rules;
}

As of WordPress 3, this no longer works. Well… it sorta works in that it keeps the proper section but redirects the browser to /tags/oranges/ (ie back to the default WP structure)

So, my question is, What’s the *right* way to do this? I’ve tried switching to use simple add_rewrite_rule commands, but those don’t yield any better results.

Thanks in advance for any help.
James W.