Ultra-deep Advanced Camera for Surveys (ACS) and WFC3/IR HUDF+HUDF09 data, along with the wide-area GOODS+ERS+CANDELS data over the CDF-S GOODS field, are used to measure UV colors, expressed as the UV-continuum slope {beta}, of star-forming galaxies over a wide range of luminosity (0.1L*_z=3_ to 2L*_z=3_) at high redshift (z~7 to z~4). {beta} is measured using all ACS and WFC3/IR passbands uncontaminated by Ly{alpha} and spectral breaks. Extensive tests show that our {beta} measurements are only subject to minimal biases. Using a different selection procedure, Dunlop et al. (2012MNRAS.420..901D) recently found large biases in their {beta} measurements. To reconcile these different results, we simulated both approaches and found that {beta} measurements for faint sources are subject to large biases if the same passbands are used both to select the sources and to measure {beta}. High-redshift galaxies show a well-defined rest-frame UV color-magnitude (CM) relationship that becomes systematically bluer toward fainter UV luminosities. No evolution is seen in the slope of the UV CM relationship in the first 1.5 Gyr, though there is a small evolution in the zero point to redder colors from z~7 to z~4. This suggests that galaxies are evolving along a well-defined sequence in the L_UV_-color ({beta}) plane (a "star-forming sequence"?). Dust appears to be the principal factor driving changes in the UV color {beta} with luminosity. These new larger {beta} samples lead to improved dust extinction estimates at z~4-7 and confirm that the extinction is essentially zero at low luminosities and high redshifts. Inclusion of the new dust extinction results leads to (1) excellent agreement between the star formation rate (SFR) density at z~4-8 and that inferred from the stellar mass density; and (2) to higher specific star formation rates (SSFRs) at z>~4, suggesting that the SSFR may evolve modestly (by factors of ~2) from z~4-7 to z~2.