Observations of electron phase-space holes (EHs) in Earth's plasma sheet by the THEMIS satellites include the first detection of a magnetic perturbation (deltaB_{ parallel}) parallel to the ambient magnetic field (B0). EHs with a detectable deltaB_{ parallel} have several distinguishing features including large electric field amplitudes, a magnetic perturbation perpendicular to B0, high speeds ( approximately 0.3c) along B0, and sizes along B0 of tens of Debye lengths. These EHs have a significant center potential (Phi approximately k_{B}T_{e}/e), suggesting strongly nonlinear behavior nearby such as double layers or magnetic reconnection.