Ultra-deep 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 in 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. 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 towards 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 still essentially zero at low luminosities and high redshifts. Inclusion of the new dust extinction results leads to (i) excellent agreement between the SFR density at z~4-8 and that inferred from the stellar mass density, and (ii) to higher SSFRs at z>~4, suggesting the SSFR may evolve modestly (by factors of ~2) from z~4-7 to z~2. ; Comment: 39 pages, 26 figures, 8 tables, accepted for publication in ApJ, updated to include results from the full CANDELS data set over the CDF South and also to use the most recent WFC3/IR zeropoint determinations