For long-standing theoretical reasons, it is often asserted that the threshold shear stress for entrainment of sedimentary particles (τ*t = ρf u*t2, made dimensionless as A = ρf u*t2/((ρp - ρf)gd)) has a universal relationship with the particle Reynolds number (Re*t = u*t d/ν), where u*t is the threshold friction velocity, ρf is the fluid density, ρp is the density of the particles, d is the particle diameter, g is the gravitational acceleration and ν is the kinematic viscosity of the fluid. However, experimental plots of A(Re*t) for sediment entrainment in air and water show two major differences: (1) For large Re*t, the values of A in water are, in general, a few times larger than those in air, and (2) when Re*t <1, A increases more rapidly in air than in water as Re*t decreases. This paper derives a new, general theory for A, which incorporates the effects of fluid turbulence, particle cohesion and probabilistic aspects of grain entrainment. It is found that difference (1) is explained by differences in the probability distribution of streamwise velocity fluctuations for typical situations in air and water, which follow from basic scaling laws for velocity variances in turbulent flow. Difference (2) is explained by the different behaviors of interparticle cohesion forces in air and water. The resulting expression is shown to compare well with experimental data.