  Recently, a new framework for solving the hierarchy problem was proposed
which does not rely on low energy supersymmetry or technicolor. The fundamental
Planck mass is at a TeV and the observed weakness of gravity at long distances
is due the existence of new sub-millimeter spatial dimensions. In this letter,
we study how the properties of black holes are altered in these theories. Small
black holes---with Schwarzschild radii smaller than the size of the new spatial
dimensions---are quite different. They are bigger, colder, and longer-lived
than a usual $(3+1)$-dimensional black hole of the same mass. Furthermore, they
primarily decay into harmless bulk graviton modes rather than standard-model
degrees of freedom. We discuss the interplay of our scenario with the
holographic principle. Our results also have implications for the bounds on the
spectrum of primordial black holes (PBHs) derived from the photo-dissociation
of primordial nucleosynthesis products, distortion of the diffuse gamma-ray
spectrum, overclosure of the universe, gravitational lensing, as well as the
phenomenology of black hole production. For example, the bound on the spectral
index of the primordial spectrum of density perturbations is relaxed from 1.25
to 1.45-1.60 depending on the epoch of the PBH formation. In these scenarios
PBHs provide interesting dark matter candidates; for 6 extra dimensions MACHO
candidates with mass $\sim 0.1M_\odot$ can arise. For 2 or 3 extra dimensions
PBHs with mass $\sim 2000 M_\odot$ can occur and may act as both dark matter
and seeds for early galaxy and QSO formation.
