XENON10 is an experiment to directly detect weakly interacting massive particle (WIMPs), which may comprise the bulk of the non-baryonic dark matter in our Universe. We report new results for spin-dependent WIMP-nucleon interactions with 129-Xe and 131-Xe from 58.6 live-days of operation at the Laboratori Nazionali del Gran Sasso (LNGS). Based on the non-observation of a WIMP signal in 5.4 kg of fiducial liquid xenon mass, we exclude previously unexplored regions in the theoretically allowed parameter space for neutralinos. We also exclude a heavy Majorana neutrino with a mass in the range of 10 GeV -2 TeV as a dark matter candidate under standard assumptions for its density and distribution in the galactic halo.