The influence of decoherence on quantum memories for photons based on atomic ensembles is discussed. It is shown that despite the large entanglement of the collective storage states, corresponding to single photons or nonclassical states of light, the sensitivity to decoherence does not scale with the number of atoms. This is due to the existence of equivalence classes of storage states, which have the same projection onto the relevant quasiparticle mode (dark-state polariton.) Several decoherence processes resulting from uncorrelated individual reservoir couplings are analyzed in detail: single-atom spin flips and dephasing, atom loss, and motion of atoms. Furthermore, it is shown that the sensitivity to collective decoherence processes that affect all polariton modes with comparable strength does also not increase with the number of atoms.