By adding atoms to the crystal basis, the space group will generally change and so will the symmetry classification of electronic states $|\psi_{nk}\rangle$. To be a bit more complete, let's look at exactly how states are classified and labeled.
If we have a symmorphic space group $\mathbb{S}$, then for a given $k$ we can define its little cogroup $\mathbb{G}_k$ (group of the wavevector) by
$$ \mathbb{G}_k = \{\:(R|0)\in \mathbb{S} \:\:\:|\:\:\: Rk\equiv k \:\} $$
where $Rk\equiv k$ means equivalence up to a reciprocal lattice vector. In a crystal, electronic states $|\psi_{nk}\rangle$ are classified by the irreducible representations of the little cogroup of $k$. Each high symmetry line in the Brillouin Zone has a single little cogroup associated with it and the irreps will then label the bands along that line.
Example
FCC with one atom basis
The basic FCC lattic has space group $Fm\bar{3}m$ (#225). If we look at the high symmetry line $\Delta:\Gamma\to X$, we can find (from this source) that the little cogroup is $4mm$ ($C_{4v}$). Then looking at the irreps here, we see there are 5 of them including one 2D irrep
FCC with two atom basis
A zincblende crystal is FCC but has a two atom basis (like CdTe). It has space group $F\bar{4}3m$ (#216). Looking at the same high symmetry line $\Delta:\Gamma\to X$, the little cogroup in this case is $2mm$ ($C_{2v}$) (as found here). $C_{2v}$ has only 4 irreps and they are all 1D. So the symmetry classification is clearly different.
