We show that many-body effects in stabilized nanocolloidal suspensions can have a profound effect on their optical nonlinearity. By considering the screened Coulomb repulsions between nanoparticles, we find that the nonlinear optical behavior of these colloids can range from polynomial to exponential depending on their composition and chemistry. The dynamics and stability properties of optical beams propagating in such nonideal gas environments of interacting colloidal particles are investigated. Our analysis provides a theoretical foundation for understanding the recently observed super-Kerr nonlinear optical response of such systems.