Colloidal particles immersed in liquid crystals frustrate orientational order. This generates defect lines known as disclinations. At the core of these defects, the orientational order drops sharply. We have discovered a class of soft solids, with shear moduli up to 10(4) pascals, containing high concentrations of colloidal particles (volume fraction phi greater than or similar to 20%) directly dispersed into a nematic liquid crystal. Confocal microscopy and computer simulations show that the mechanical strength derives from a percolated network of defect lines entangled with the particles in three dimensions. Such a "self-quenched glass" of defect lines and particles can be considered a self-organized analog of the "vortex glass" state in type II superconductors.