We present new constraints on the evolution of the early-type galaxy color-magnitude relation (CMR) based on deep near-infrared imaging of a galaxy protocluster at z=2.16 obtained using NICMOS on-board the Hubble Space Telescope. This field contains a spectroscopically confirmed space-overdensity of Lyman-alpha and H-alpha emitting galaxies which surrounds the powerful radio galaxy MRC 1138-262. Using these NICMOS data we identify a significant surface-overdensity (= 6.2x) of red J-H galaxies in the color-magnitude diagram (when compared with deep NICMOS imaging from the HDF-N and UDF). The optical-NIR colors of these prospective red-sequence galaxies indicate the presence of on-going dust-obscured star-formation or recently formed (<~ 1.5 Gyr)stellar populations in a majority of the red galaxies. We measure the slope and intrinsic scatter of the CMR for three different red galaxy samples selected by a wide color cut, and using photometric redshifts both with and without restrictions on rest-frame optical morphology. In all three cases both the rest-frame $U-B$ slope and intrinsic color scatter are considerably higher than corresponding values for lower redshift galaxy clusters. These results suggest that while some relatively quiescent galaxies do exist in this protocluster both the majority of the galaxy population and hence the color-magnitude relation are still in the process of forming, as expected.