LDO Regulators are notorious for self oscillation. And, according to the datasheet, this one appears to be more sensitive to output capacitor ESR than most -- probably because of the higher current capability. The datasheet has a couple of graphs that show stable operation regions, for the output capacitor -- it's important to conform to this.
In other words, my guess would be that your Regulator is oscillating.
Also, circuit layout may be an issue. The capacitor needs to be as close to the regulator as possible.
BTW: make sure you're using an electrolysis capacitor! ;D [joking!]