The main noise source in detection of faint companions such as extrasolar planets near bright stars with AO is speckle noise--residual PSF structure caused by wavefront errors due to the atmosphere, the AO system, and static optical effects. Of these, the most fundamental are atmospheric speckles--even given infinite wavefront SNR and a perfect DM, timelag between sensing and correction will always lead to a residual atmospheric speckle pattern. There have been several suggestions as to the lifetime of these atmospheric speckles, none strongly supported by theory or simulation. We have carried out a systematic series of simulations and analysis to explore this question. We show that speckles have different behavior in the regime in which diffraction is significant (first-order speckles, which are rapidly modulated as a phase error translates across the aperture) and in the coronagraphic regime (second-order speckles, which evolve only as the phase screen completely clears the aperture.). We use simulations to analyze the behavior of speckles in a variety of regimes, showing that the second-order atmospheric speckle lifetime is almost constant irrespective of the properties of the AO system, and is set primarily by the atmospheric clearing time of the telescope aperture.