Early Christians were battling Gnosticism and many other unwelcome pagan influences. Just because it is from the early days of the Church does not necessarily make it correct and true.
However, since it was Gnosticism they were battling, what better way would there be to fight it, than by honoring the relics of the saints? It's the Gnostics, precisely, who took the anti-body, anti-physical view.
The gnostics --- the great rivals of the Catholic Christians --- taught that people should shun the material world created by the evil demiurge, and embrace the spiritual world.
Gnostics associated evil with matter and flesh. They were convinced of the worthlessness of anything that suggested mortality, e.g. a dead man's bones.
The veneration by Christians of the mortal remains of the martyrs is a forceful refutation of Gnosticism. We don't believe flesh is either evil or irrelevant. We believe in Jesus, the Word-made-Flesh. We believe in the Resurrection of the Body.
Early Christianity lost out to Paul!