The mechanical properties of concentrated dispersions of sterically-stabilised colloidal particles in nematic hosts are explored using a combination of optical microscopy and viscoelastic shear measurements. Starting from an initially homogeneous dispersion in an isotropic host, it is found that the kinetics of the isotropic-nematic transition lead to the formation of a percolated particle network that imparts surprising mechanical rigidity to the resulting colloid/liquid crystal composite. Specifically, the viscoelastic storage modulus G, is observed to rise by approximately 5 orders of magnitude within a few degrees of the bulk isotropic-nematic transition temperature. Using 4-4'pentyl cyano-biphenyl as the solvent, the composite at room temperature is a self-supporting soft solid over a wide range of particle concentrations. The particle microstructure depends sensitively on thermal treatment and particle concentration and it is found that faster cooling enhances the visoelastic moduli of the composite. Also, several classes of network topology have been identified. In all cases studied to date, the particles can be redispsersed upon heating the solvent through the nematic-isotropic transition. The formation of the composite is therefore thermally reversible. A rigorous theory to account for the observed mechanical properties is not currently available.