My datasheet for this part specifies a 10uF tantalum capacitor for the output. These have very low ESR (resistance). I'm guessing the 100uF capacitor you show is a common electrolytic, which will have much higher ESR.
LDO regulators like these are more complex than an average linear regulator, and so have a slower feedback loop; which gives them a tendency to oscillate if specific conditions are not met on the output pin. Especially ESR! I've designed several as an exercise in SPICE and found ESR of the output caps to be absolutely critical to stability.
If you don't have the tantalum cap, try using a ceramic cap in parallel as suggested. It's often sufficient, though you may need a 1uF or 10uF, instead of a 0.1uF.
And of course, rule out other possibilities if you haven't already, like excessive current drain for example.