We consider a spin-orbit coupled particle confined in a quantum dot in a bath of impurity spins. We investigate the consequences of spin-orbit coupling on the interactions that the particle mediates in the spin bath. We show that in the presence of spin-orbit coupling, the impurity-impurity interactions are no longer spin conserving. We quantify the degree of this symmetry breaking and show how it relates to the spin-orbit coupling strength. We identify several ways how the impurity ensemble can in this way relax its spin by coupling to phonons. A typical resulting relaxation rate for a self-assembled Mn-doped ZnTe quantum dot populated by a hole is 1 mu s. We also show that decoherence arising from nuclear spins in lateral quantum dots is still removable by a spin echo protocol, even if the confined electron is spin-orbit coupled. DOI: 10.1103/PhysRevB.87.165303