Instantiated object material colors

I'm instantiating objects that then change color individually based on environmental factors. The problem is that that as the number of objects grow, so does the number of materials, and the game slows dramatically. Is there a good way to instantiate objects with (Ideally) the same material but different colors without racking up an obscene number of draw calls? Maybe I'm going about this all wrong.

Assuming that replacing Mesh uv's is not as expensive as multiple draw calls (which is most likely the case), you could create a texture containing all/many possible color shades, and then set all uv's of a mesh that needs to be a certain color to the specific value that maps to the pixel containing the desired color. If your mesh is already textured, you could use Mesh.uv2 and multi-texturing.

If you want a pixel-precise mapping with all possible RGB shades (24bit), you'd need a 4k x 4k texture which is set to point samling. For 16bit color resolution you'll need just 256x256. However, you could also let the bilinear filtering work for you and just create a low-resolution texture, instead of trying to represent each color shade as an individual pixel.

EDIT: You'd also need to use the CombineChildren script to the parent object of all your individually colored objects, otherwise each object will still be rendered by itself with separate drawcalls.