add_rewrite_rule() vs $wp_rewrite->rules vs ‘rewrite_rules_array’?

First of all use add_rewrite_rule() over messing directly with $wp_rewrite->rules if possible. The latter is a bit low-level.

Regarding the ‘url not updating’ – this isn’t the job of the rewrite rules. These simply point urls to their content, but they don’t update the user’s address bar.

The file that is responsible for this is /wp-includes/canonical.php. In particular the function redirect_canonical() hooked onto template_redirect.

This redirect_canonical() has its own filter:

add_filter('redirect_canonical', 'wpse50912_redirect_canonical',10,2)
function wpse50912_redirect_canonical($redirect_url, $requested_url){

     //Do stuff - determine if url is requesting album/track and check
     //If it is, check it is using the new structure. 
     //Return the url you want in the address bar.

     return $redirect_url;
}