i see your point, "both" suggests that their combined ages date back 1000 years. but since the first part of the sentence establishes a common element between the two doesn't that clarify the use of "both"? for example, if someone asked, "which tribe, the acoma or the hopi, dates back 1000 years?", you could say "both do".
granted, an answer like "each dating back" or "each of which date back" would be the best choice, but those are not provided. the rest of the choices containing "each" just don't sound right.