Database error when searching for certain relationship types

Advanced Search fails with a "DB Error: no such field" when searching by relationship when the relationship label is the same in both directions. That is, "Parent of/Child of" relationships do not fail, but "Spouse of" or "Partner of" does.

To replicate on demo server, go to Advanced Search, and under Relationships, select "Spouse of" and press Search.

Error details follow, and suggest that perhaps this is a side effect of CRM-16151.

{{Database Error Code: Unknown column 'contact_b.is_deleted' in 'where clause', 1054
Additional Details:

Array
(
[callback] => Array
(
[0] => CRM_Core_Error
[1] => handle
)

[code] => -19
[message] => DB Error: no such field
[mode] => 16
[debug_info] =>
CREATE TEMPORARY TABLE civicrm_rel_temp_54183a828501cbee473ada5256b17dc8
(SELECT contact_id_b as contact_id, civicrm_relationship.id
FROM civicrm_relationship
INNER JOIN civicrm_contact c ON civicrm_relationship.contact_id_a = c.id
WHERE (
civicrm_relationship.is_active = 1 AND
( civicrm_relationship.end_date IS NULL OR civicrm_relationship.end_date >= 20150610 ) AND
( civicrm_relationship.start_date IS NULL OR civicrm_relationship.start_date <= 20150610 )
) AND (contact_b.is_deleted = 0) AND civicrm_relationship.relationship_type_id = 11 )
UNION
(SELECT contact_id_a as contact_id, civicrm_relationship.id
FROM civicrm_relationship
INNER JOIN civicrm_contact c ON civicrm_relationship.contact_id_b = c.id
WHERE (
civicrm_relationship.is_active = 1 AND
( civicrm_relationship.end_date IS NULL OR civicrm_relationship.end_date >= 20150610 ) AND
( civicrm_relationship.start_date IS NULL OR civicrm_relationship.start_date <= 20150610 )
) AND (contact_b.is_deleted = 0) AND civicrm_relationship.relationship_type_id = 11 )
[nativecode=1054 ** Unknown column 'contact_b.is_deleted' in 'where clause']
[type] => DB_Error
[user_info] =>
CREATE TEMPORARY TABLE civicrm_rel_temp_54183a828501cbee473ada5256b17dc8
(SELECT contact_id_b as contact_id, civicrm_relationship.id
FROM civicrm_relationship
INNER JOIN civicrm_contact c ON civicrm_relationship.contact_id_a = c.id
WHERE (
civicrm_relationship.is_active = 1 AND
( civicrm_relationship.end_date IS NULL OR civicrm_relationship.end_date >= 20150610 ) AND
( civicrm_relationship.start_date IS NULL OR civicrm_relationship.start_date <= 20150610 )
) AND (contact_b.is_deleted = 0) AND civicrm_relationship.relationship_type_id = 11 )
UNION
(SELECT contact_id_a as contact_id, civicrm_relationship.id
FROM civicrm_relationship
INNER JOIN civicrm_contact c ON civicrm_relationship.contact_id_b = c.id
WHERE (
civicrm_relationship.is_active = 1 AND
( civicrm_relationship.end_date IS NULL OR civicrm_relationship.end_date >= 20150610 ) AND
( civicrm_relationship.start_date IS NULL OR civicrm_relationship.start_date <= 20150610 )
) AND (contact_b.is_deleted = 0) AND civicrm_relationship.relationship_type_id = 11 )
[nativecode=1054 ** Unknown column 'contact_b.is_deleted' in 'where clause']
[to_string] => [db_error: message="DB Error: no such field" code=-19 mode=callback callback=CRM_Core_Error::handle prefix="" info="
CREATE TEMPORARY TABLE civicrm_rel_temp_54183a828501cbee473ada5256b17dc8
(SELECT contact_id_b as contact_id, civicrm_relationship.id
FROM civicrm_relationship
INNER JOIN civicrm_contact c ON civicrm_relationship.contact_id_a = c.id
WHERE (
civicrm_relationship.is_active = 1 AND
( civicrm_relationship.end_date IS NULL OR civicrm_relationship.end_date >= 20150610 ) AND
( civicrm_relationship.start_date IS NULL OR civicrm_relationship.start_date <= 20150610 )
) AND (contact_b.is_deleted = 0) AND civicrm_relationship.relationship_type_id = 11 )
UNION
(SELECT contact_id_a as contact_id, civicrm_relationship.id
FROM civicrm_relationship
INNER JOIN civicrm_contact c ON civicrm_relationship.contact_id_b = c.id
WHERE (
civicrm_relationship.is_active = 1 AND
( civicrm_relationship.end_date IS NULL OR civicrm_relationship.end_date >= 20150610 ) AND
( civicrm_relationship.start_date IS NULL OR civicrm_relationship.start_date <= 20150610 )
) AND (contact_b.is_deleted = 0) AND civicrm_relationship.relationship_type_id = 11 )
[nativecode=1054 ** Unknown column 'contact_b.is_deleted' in 'where clause']"]
)
}}