EDIT:
you must call your filter after the shortcode is processed, giving it priority > 10, and you must match on a multiline expression.
Try this work with my installation and using the standard gallery shortag:
add_filter( 'the_content', 'remove_br_gallery', 11, 2);
function remove_br_gallery($output) {
return preg_replace('/<br style=(.*)>/mi','',$output);
}