How much do you want to pay? You can get arbitrarily good power for arbitrarily large sums of money :-)I'd recommend a low-ripple regulator, and a significantly larger capacitor, and perhaps a HF choke. Say, a 2 uH choke, followed by a 470 uF capacitor.
If your raw supply is 15V why not use a 7808 followed by a 7805? Share the heat, double the supply ripple rejection at least. (Unless the ripple is due to the load?)
With a 7805, you just need an output capacitor. Typically, minimum 10 uF, but more is generally better (up to a limit of a few thousand uF).
Check out that $4 component I linked to, though -- it's a miniature switching regulator in a package that fits in the same footprint as a TO-220 7805, but it generates less heat.
If it's just a 328 and a couple LEDs, it can hardly be more than 50mA, yes?
I am using a 2200uf capacitor on the input of the 7805 then on it output I am using a 10uf cap..
However, are you SURE it's the power? It may just as well be the sensor you're hooking up to the analog input. Or the analog input itself. Are you buffering it? Does the sensor provide enough current? Is the sensor interference free?