Let μ be a rational-valued metric on a finite set T. We consider (a version of) the multifacility location problem: given a finite set V T and a function c:V2->Z + , attach each element x V-T to an element γ(x) T minimizing c(xy)μ(γ(x)γ(y)):xy V2, letting γ(t) t for each t T. Large classes of metrics μ have been known for which the problem is solvable in polynomial time. On the other hand, Dalhaus et al. (SIAM J. Comput. 23 (4) (1994) 864) showed that if T={t 1 ,t 2 ,t 3 } and μ(t i t j )=1 for all i<>j, then the problem (turning into the minimum 3-terminal cut problem) becomes strongly NP-hard. Extending that result and its generalization in (European J. Combin. 19 (1998) 71), we prove that for μ fixed, the problem is strongly NP-hard if the metric μ is nonmodular or if the underlying graph of μ is nonorientable (in a certain sense).