Adding a 1k resistor to the output didn't change anything, but thanks for the tip, I'll keep that in mind.
I found where it shows that I need at least a 3V difference, but boy was that worded weirdly. Maybe it's in English somewhere else on the sheet.
Did a little research, and I started looking for a "low-dropout" voltage regulator. So far I'm not finding one to suit my needs, but i'll keep looking.
Do you have a recommendation off the top of your head?