It is rare that there is too much decoupling. The only case I have ever encounters is that some DC to DC converters will not start with too much of a capacitave load, and the odd case of low dropout regulators, most are not that fussy.
If you put too much in isn't it a bit like shorting out the power supply at startup?
It depends upon how you define decoupling, eg small ceramic caps or large electrolytics. The term has
been used both ways on this thread. The following people use decoupling to refer to the former, small
ceramics.
http://www.hottconsultants.com/techtips/decoupling.html
A lot of small value caps will likely have little effect on startup. OTOH, if the values of the electrolytics
are too high, then the power supply may be slow in starting up, and possibly affect bootup of the
microcontroller, but I wouldn't think this would be a problem in general, unless the values are really
high, say over 100 or 500 uF, depending on the circuit.
The only reference I could find to this in the 328P d/s was the following, and they're not referring to
boot-up, although by heavily filtered they certainly mean the electrolytics.
"In heavily filtered power supplies, VCC is likely to rise or fall slowly on power-up/down. This causes
the device for some period of time to run at a voltage lower than specified as minimum for the clock
frequency used."