Ufff... Claro, tienes que poner un && allí...
Código PHP:
Ver originalelseif ( is_page() && !is_page('my-contact-page') ) :
get_template_part( 'header', 'other-page' );
endif;
Le estás diciendo que si es cualquier página y no la de contactos que muestre header-otra.php
Saludos.