  We present Keck/DEIMOS spectroscopy of stars in 8 of the newly discovered
ultra-faint dwarf galaxies around the Milky Way. We measure the velocity
dispersions of Canes Venatici I and II, Ursa Major I and II, Coma Berenices,
Hercules, Leo IV and Leo T from the velocities of 18 - 214 stars in each galaxy
and find dispersions ranging from 3.3 to 7.6 km/s. The 6 galaxies with absolute
magnitudes M_V < -4 are highly dark matter-dominated, with mass-to-light ratios
approaching 1000. The measured velocity dispersions are inversely correlated
with their luminosities, indicating that a minimum mass for luminous galactic
systems may not yet have been reached. We also measure the metallicities of the
observed stars and find that the 6 brightest of the ultra-faint dwarfs extend
the luminosity-metallicity relationship followed by brighter dwarfs by 2 orders
of magnitude in luminosity; several of these objects have mean metallicities as
low as [Fe/H] = -2.3 and therefore represent some of the most metal-poor known
stellar systems. We detect metallicity spreads of up to 0.5 dex in several
objects, suggesting multiple star formation epochs. Having established the
masses of the ultra-faint dwarfs, we re-examine the missing satellite problem.
After correcting for the sky coverage of the SDSS, we find that the ultra-faint
dwarfs substantially alleviate the discrepancy between the predicted and
observed numbers of satellites around the Milky Way, but there are still a
factor of ~4 too few dwarf galaxies over a significant range of masses. We show
that if galaxy formation in low-mass dark matter halos is strongly suppressed
after reionization, the simulated circular velocity function of CDM subhalos
can be brought into approximate agreement with the observed circular velocity
function of Milky Way satellite galaxies. [slightly abridged]
