We study a transverse instability of the nonlinear equilibria known as electron phase-space holes in the presence of a magnetic field. The instability is intrinsically two dimensional and is determined by the dynamics of the trapped electrons. It depends on hole amplitudes, ambient magnetic fields, and the perpendicular velocity spread. The long-standing hole stability problem in multiple dimensions can be characterized by the gyro-to-bounce frequency ratio. A low ratio associated with a small perpendicular velocity spread results in a disintegration of the positive potential spikes.