Upper Paleolithic Textiles from Dzudzuana Cave, Most ancient coloured twine found.

30,000 year old coloured cord found in Georgia. Two stories - one from the BBC, one from About.com.

From the BBC.

A Georgian cave has yielded what scientists say are the earliest examples of humans making cords.

The microscopic fibres, discovered accidentally while scientists were searching for pollen samples, are around 30,000 years old.
A team reports in the journal Science that ancient humans probably used the plant fibres to carry tools, weave baskets or make garments. Some of the fibres are coloured and appear to have been dyed. The fibres were discovered preserved within layers of mud in Dzudzuana Cave in Georgia.
"It's impossible to know exactly how they were used, but some of them are twisted," said Ofer Bar-Yosef, a researcher from Harvard University in the US who took part in the study.
"This is a very old principle of making rope and cord."
Only microscopic pieces of the fibres were still evident in the cave.

And from About.com - Upper Paleolithic Textiles from Dzudzuana Cave.

Archaeological investigations at Dzudzuana Cave, in the Republic of Georgia, have recovered flax (Linum usitatissimum) fibers from four Upper Paleolithic occupations. The earliest of the occupations at Dzudzuana is dated between 26,000 and 32,000 radiocarbon years before the present (RCYBP) which calibrates to between 31,000 to 36,000 cal BP. The fibers are among the oldest evidence of the use of fiber technology, but unlike other examples, Dzudzuana cave offers details about the use of fibers unrecognized to date. The Dzudzuana Cave flax fibers have clearly been modified, cut, twisted and even dyed gray, black, turquoise and pink, most likely with locally available natural plant pigments.

Perishable materials, including cordage, nets, wood and textiles, have long been recognized as an important piece of hunter-gatherer technology in the Upper Paleolithic; but it is a technology that is nearly invisible to modern archaeologists because the organic materials are so rarely preserved. Some instances of cord and textile preservation include Iron Age bog bodies, the Bronze Age Ice Man, and Archaic period Windover Bog; but for the most part, organic fibers do not survive to the modern day.