The CSP of a first-order theory T is the problem of deciding for a given finite set S of atomic formulas whether (Formula Presented) is satisfiable. Let T₁ and T₂ be two theories with countably infinite models and disjoint signatures. Nelson and Oppen presented conditions that imply decidability (or polynomial-time decidability) of (Formula Presented) under the assumption that CSP(T₁) and CSP(T₂ are decidable (or polynomial-time decidable). We show that for a large class of ω-categorical theories T₁, T₂ the Nelson-Oppen conditions are not only sufficient, but also necessary for polynomial-time tractability of (Formula Presented) (unless P = NP).