Add a URL prefix to permalinks of News category and sub-categories of posts only

add_action( 'init', 'wpa_category_base' );
function wpa_category_base() {
    // Remember to flush the rules once manually after you added this code!
    add_rewrite_rule(
        // The regex to match the incoming URL
        'news/([^/]+)/([^/]+)/([^/]+)(/[0-9]+)?/?$',
        // The resulting internal URL
        'index.php?category_name=$matches[1]/$matches[2]&name=$matches[3]&paged=$matches[4]',

        // Add the rule to the top of the rewrite list
        'top' );
}

Custom permalink structure: /media/%category%/%postname%/ Category base: .

Worked for me, WordPress 3.4.1, without any related plugins.

Try

add_action( 'init', 'wpa_category_base' );
function wp_category_base() {
// Remember to flush the rules once manually after you added this code!
    add_rewrite_rule(
    // The regex to match the incoming URL
    'news/([^/]+)/([^/]+)/([^/][^f][^e][^e][^d]+)(/[0-9]+)?/?$', //here my changes to exclude 'feed'
    // The resulting internal URL
    'index.php?category_name=$matches[1]/$matches[2]&name=$matches[3]&paged=$matches[4]',
    // Add the rule to the top of the rewrite list
    'top' );
}