Flush Rewrite Rules when new site is created on network

You need to create a hook for wpmu_new_blog action:

add_action( 'wpmu_new_blog', 'wpse8170_wpmu_new_blog' );
function wpse8170_wpmu_new_blog( $blog_id ) {
    switch_to_blog( $blog_id );
    flush_rewrite_rules();
    restore_current_blog();
}