I believe this problem is less to do with the rewrite rule, which on the face of it looks like it should work, and more to do with WordPress’ canonical redirect.
Basically when WordPress receives an url – it interprets it as a query. It then looks again at the url to check that the url is ‘correct’ (or canonical). For instance it may have superfluous forward slashes and so forth.
If the url is deemed ‘incorrect’ – you are redirected to the ‘correct’ url. The idea is that you don’t have multiple urls pointing the same content (they are all redirected to one canonical url).
The file that is responsible for this is /wp-includes/canonical.php. In particular the function redirect_canonical() is hooked onto the template_redirect action. The redirect_canonical() function has its own filter:
add_filter('redirect_canonical', 'wpse50912_redirect_canonical',10,2)
function wpse50912_redirect_canonical($redirect_url, $requested_url){
//Check the requested url is an url for your (paginated) music archive
//Return the url you want in the address bar.
return $redirect_url;
}
You can disable canonicalisation – by unhooking the redirect_canonical function from the template_redirect hook. Or can modify its behaviour using the redirect_canonical. Either way I would recommend disabling temporarily in order to verify this is the cause.