DNA degradation half-lifetime within fossilized/frozen species is ~ 500 years., even when the conditions are perfect for preservation.
Thus, in theory, if we could sequence anything that is less then 13 000 years old (expected length of preserved nucleotide sequences ~30 bp, which is just enough to stitch together two unique regions). If we have several copies of DNA (several cells), we can go a little bit further by sequencing same reads several times. If we assume an average cell is 30 um in diameter, we have ~40 000 cells in a cubic mm of tissue samle. this will allow us to extend the sequencing horizon by another 8000 years. With a cubic sample of intact, perfectly preserved tissue (this is REALLY A LOT and REALLY RARE) we could get an additional 5000 years, limiting our possibility to know the genome, let alone reproduce it to 26-30 000 years.
By using a couple of sequence assembly tricks, such as existence of reference genomes of closely related species, we could either decrease the amount of tissue sames or allow the DNA to get a little bit more degraded. However, even with a cubic centimeter of tissue we won't be able to go beyond 50-100 000 years.
The furthest we have gotten now is a Neanderthal sequence (~30 000 years) and it was already tough. It would be impossible to get a hand on dinasaurus DNA sequence, let alone trying to clone it. Mammoth, Saber-tooth Tiger and Dodo should be ok, provided we can find their remainders.
Now, Once you get the raw DNA sequence, you have to get the epigenetic code right, find a compatible egg of a related spicies (that is quite hard), inject your DNA into it, and hopefully, with lots of ifs you can get your clone and hope it survives. However the part about getting the epigenetic code right and finding a compatible egg is really not easy. Personally, I won't parry on anything that doesn't have close related species still living.
UPDATE: as of June 2013 a genome of a wild horse 700 000 years old have been sequenced, which is the furthers we could get so far.