You should try setting ‘slug’ ( in the ‘rewrite’ parameter/option) to ‘our-firm/shareholders’, just like the structure you have set in the add_rewrite_rule() function.
The first parameter of add_rewrite_rule() and the ‘rewrite’ setting of the custom post type must be equal in order to get the rewritting actually working.
So, in case you choose coding the registration of the custom post type, your register_post_type() should look something like this:
$args = array( 'rewrite' => array( 'our-firm/shareholders', 'with_front' => true ) );
register_post_type( 'shareholder', $args );
Of course you need to fill the $args array with some other keys. I’ve just specified ‘rewrite’ to keep the explanation simple. Follow the documentation on this function to craft a proper registration: http://codex.wordpress.org/Function_Reference/register_post_type
If changes are not reflected, then try flushing the rewrite rules. You can accomplish this in a safety way by clicking on “Save Changes” in Admin Page > Settings > Permalinks