Liquid xenon is an important detection medium in direct dark matter experiments, which search for low-energy nuclear recoils produced by the elastic scattering of WIMPs with quarks. The two existing measurements of the relative scintillation efficiency of nuclear recoils below 20 keV lead to inconsistent extrapolations at lower energies. This results in a different energy scale and thus sensitivity reach of liquid xenon dark matter detectors. We report a new measurement of the relative scintillation efficiency below 10 keV performed with a liquid xenon scintillation detector, optimized for maximum light collection. Greater than 95% of the interior surface of this detector was instrumented with photomultiplier tubes, giving a scintillation yield of 19.6 photoelectrons/keV electron equivalent for 122-keV γ rays. We find that the relative scintillation efficiency for nuclear recoils of 5 keV is 0.14, staying constant around this value up to 10 keV. For higher energy recoils we measure a value of 0.21, consistent with previously reported data. In light of this new measurement, the XENON10 experiment's upper limits on spin-independent WIMP-nucleon cross section, which were calculated assuming a constant 0.19 relative scintillation efficiency, change from 8.8×10-44 cm2 to 9.9×10-44 cm2 for WIMPs of mass 100 GeV/c2, and from 4.5×10-44 cm2 to 5.6×10-44 cm2 for WIMPs of mass 30 GeV/c2.