I live in Denmark and am studying Danish and linguistics here. I'm fairly certain that what you guys are getting thrown off by is the stød in the "te" sound. To someone who isn't used to hearing Danish, the stød, or the glottal stop, can potentially distort the way you hear the "t". As I mentioned previously, this phenomenon is stronger in the Copenhagen accent. I personally hear the "t" aspirated perfectly clear.
Ok, to be correct and precise: it sounds like "ts" to my ears (and the others who have the same pronunciation of "t") because the "t" in my native language is a bit softer. For English and German speaking it sounds very normal. Unfortunately I can't record it here- you would hear the difference. Sorry for inaccuracy!
I think perhaps that you're talking about aspiration, which is when the pronunciation of a consonant produces a puff of air from the mouth. In Danish, the consonants p, t and k are aspirated. The rest aren't. This produces a slightly different sound from languages that do not use aspiration, like Russian or Spanish.
Looking at this image of the mouth, the aspirated t is produced by placing the tip of the tongue at the alveolar ridge. An unaspirated t is usually dental, so the tongue is further to the front of the mouth.
This is different from the ts sound like Russian ц or the c sound you'll find in many Slavic languages that use the Latin alphabet.
Your absolutely right! That's the thing. What I meant- to the speakers of the "unaspirated-t-languages" it really often sounds like "c", though. :D:D I can hear it from my 6 years old son- he lives in DK longer than I do and he always corrects me that I have to say "ts" instead of "t". This is what he hears. :) Goddag! ;)