This is a brutally complicated question that is the source of lots of debate. There is no one answer, or even much in the way of settled opinion. Three points that I think are possible, partial answers:

1. Roman religion was fairly syncretic, the Romana were willing to assimilate foreign cults in many situations, so the rise of new religions was not an issue, so long as they were willing to nod at Greco-Roman cosmology in some fashion. 'Conversion' to most traditions didn't require rejection of one's former faith (or identity). One of Christianity's major issues, vs the mystery religions, was that it's rejection of other gods was considered atheism, and led to familial and civic rejection.

2. Well before the rise of the religious groups you spoke of there was some awareness among some Romans that there was something... not quite right... with their religious tradition. Many Roman philosophical schools were quite fatalistic, rejecting the invocation/intercession of the traditional gods as being possible or plausible, while some rejected the Greco-Roman mythology entirely over the immorality of the gods as portrayed in narrative.

3. Many of new religious movements offered explicit paths to salvation through ritual, wisdom or divine intercession, something that the Greco-Roman tradition didn't emphasize quite as much. Christianity also offered another form of rescue to many through charity, which some scholars think had significant appeal to both patrons and petitioners. Add to that the sense of community these groups built through ritual, and they provided another sense of security through belonging.

People will hopefully add more, but in my studies these seem to have been significant factors.

I would venture to suggest that they only seem as though they were "competing" because you, as a learned person living roughly two thousand years later, know how history played out. We know who "won," and we have some sense of the major religions and cults that died out, but keep in mind that Christianity grew slowly within a period of a couple hundred years before beginning to really take hold in the later empire in the 300s. Assuming that these religious ideas were outwardly competing against one another simplifies the historical situation a little too much-- it excludes the possibility of natural assimilation via family ties (which we know happened), and it also assumes that the ideologies were similar enough to compete with one another.

What we refer to as "traditional Roman religion" was not a religion in the sense that we think of Christianity as a religion; gods could be tied to the state, the household, the region, etc, and all communication with this god involved a direct action of sacrifice, offerings, or other highly varied rituals. It's difficult to generalize, but the evidence we have for these cults does not suggest any overwhelming personal religious ideology or relationship with the deities beyond this system of offering and appeasement. That is not to say that it isn't just as complex-- in fact, more so, but it doesn't mean that the competition was ideologically based.

This is really a complex subject and I apologize for my scattered thoughts, but if you'd like to check out something really interesting, read about the city of Dura Europos in Syria and the excavations that have produced evidence of mystery cults (a Mithraeum, for example), a Christian sanctuary, and a synagogue, the followers of which lived side-by-side amongst each other in the city. I'm studying under a historian who's published on Dura and spent lots of time there before it was destroyed, and it's such a fascinating place!