  In gauge-mediated supersymmetry breaking theories the next-to-lightest
supersymmetric particle can decay during or after the nucleosynthesis epoch.
The decay products such as photons and hadrons can destroy the light element
abundances. Restricting the damage that these decays can do leads to
constraints on the abundance and lifetime of the NLSP. We compute the freezeout
abundance of the NLSP by including all coannhilation thresholds which are
particularly important in the case in which the NLSP is the lightest stau. We
find that the upper bound on the messenger scale can be as stringent as 10^12
GeV when the NLSP is the lightest neutralino and 10^13 GeV when the NLSP is the
lightest stau. Our findings disfavour models of gauge mediation where the
messenger scale is close to the GUT scale or results from balancing
renormalisable interactions with non-renormalisable operators at the Planck
scale. When combined with the requirement of no gravitino overabundance, our
bound implies that the reheating temperature after inflation must be less than
10^7 GeV.
