"A cloth tape covered in a layer of glue - this seems simple enough that it could be made even with ancient technology, right"
Lets look at what exactly duct tape is made out of to find out for sure!
The original 'duck' tape used cotton duck cloth as its backing. The word 'duck' actually comes from Dutch for linen canvas. Tight woven canvasses of linen became readily used for painting, shields, and sails by the late middle ages in Europe; cotton versions were not as strong but lighter. My research is quasi-inconclusive, but it appears that tight woven canvas was not used by the Greeks and Romans, who used lighter linen sails. The Arabs used lighter woven hemp sails.
In any case, appropriate cloth is available by the Medieval period at the latest, possibly much earlier.
Wikipedia's amazing Chemistry of pressure-sensitive adhesives comes in handy here! Basically, adhesive tape depended on the presence of rubber at first. An example would be a mixture of rosin and rubber. Now both of these are natural ingredients, and both are in fact tree sap. So we can conclude that the ingredients are all present by the middle ages at the latest.
Problems and Solutions
However, there is a problem. The first is that these resources are found in widely different areas. Rosin comes from pine trees and wild rubber from rubber trees; one is at home in temperate and/or mountainous regions, the other in the lowland tropics. This can be overcome by two ways. The first is to make a world where these regions are adjacent to each other. The Mexican highlands are filled with pine, and the nearby Yucutan is a lowland rainforest; make these areas larger and have your civilization develop there. The second is to invent new plants. The Germans tried to extract natural rubber from dandelions, which contain small amounts of latex. They were unsuccessful, but if you invented a much more latex-y dandelion plant that lived in temperate environments with pine trees, then the ingridents would be together.