We select 25,000 galaxies from the NEWFIRM Medium Band Survey (NMBS) to study the rest-frame U-V color distribution of galaxies at 0 < z < 2.5. The five unique NIR filters of the NMBS enable the precise measurement of photometric redshifts and rest-frame colors for 9,900 galaxies at 1 < z < 2.5. The rest-frame U-V color distribution at all z<~2.5 is bimodal, with a red peak, a blue peak, and a population of galaxies in between (the green valley). Model fits to the optical-NIR SEDs and the distribution of MIPS-detected galaxies indicate that the colors of galaxies in the green valley are determined largely by the amount of reddening by dust. This result does not support the simplest interpretation of green valley objects as a transition from blue star-forming to red quiescent galaxies. We show that correcting the rest-frame colors for dust reddening allows a remarkably clean separation between the red and blue sequences up to z~2.5. Our study confirms that dusty starburst galaxies can contribute a significant fraction to red sequence samples selected on the basis of a single rest-frame color (i.e. U-V), so extra care must be taken if samples of truly red and dead galaxies are desired. Interestingly, of galaxies detected at 24 microns, 14% remain on the red sequence after applying the reddening correction.