How can you store your option at the permalink settings page?

I ran into this very same issue and I have a workaround. Hopefully it will be fixed in the upcoming 3.3 release as this trac ticket suggests.

The workaround basically replicates the important bits of the wp-admin/options.php file where settings registered via the settings API are processed.

The reason additional permalink settings do not currently update is because the options-permalink.php page posts back to itself rather than to options.php so no handling of your registered settings occurs.

The following code placed in your theme or plugin will get things working:

// add a very low priority action to make sure any extra settings have been added to the global
add_action( 'admin_init', 'enable_permalink_settings', 999999 );
function enable_permalink_settings() {
    global $new_whitelist_options;

    // save hook for permalinks page
    if ( isset( $_POST['permalink_structure'] ) || isset( $_POST['category_base'] ) ) {
        check_admin_referer('update-permalink');

        $option_page="permalink";

        $capability = 'manage_options';
        $capability = apply_filters( "option_page_capability_{$option_page}", $capability );

        if ( !current_user_can( $capability ) )
            wp_die(__('Cheatin’ uh?'));

        // get extra permalink options
        $options = $new_whitelist_options[ $option_page ];

        if ( $options ) {
            foreach ( $options as $option ) {
                $option = trim($option);
                $value = null;
                if ( isset($_POST[$option]) )
                    $value = $_POST[$option];
                if ( !is_array($value) )
                    $value = trim($value);
                $value = stripslashes_deep($value);
                update_option($option, $value);
            }
        }

        /**
         *  Handle settings errors
         */
        set_transient('settings_errors', get_settings_errors(), 30);
    }
}