That's unlikely the problem: even at 1000u, to generate a time constant of even fractions of a second requires output impendance improbably high for any power supply / regulator.
The issue here is likely something else. For example I have a crystal oscillator with Rf that takes 5 - 7 seconds to start, longer in a clean environment.
As to decoupling, many people confuse bulk decoupling with (local) decoupling. They are so different that what works for one almost surely don't work for the other.