The unambiguous detection of dark matter annihilation in our Galaxy would unravel one of the most outstanding puzzles in particle physics and cosmology. Recent observations have motivated models in which the annihilation rate is boosted by the Sommerfeld effect, a nonperturbative enhancement arising from a long-range attractive force. We applied the Sommerfeld correction to Via Lactea II, a high-resolution N-body simulation of a Milky Way-sized galaxy, to investigate the phase-space structure of the galactic halo. We found that the annihilation luminosity from kinematically cold substructure could be enhanced by orders of magnitude relative to previous calculations, leading to the prediction of gamma-ray fluxes from as many as several hundred dark clumps that should be detectable by the Fermi satellite.