Christianity was doing fine before Constantine, so there's no reason to think it would suddenly become screwed just because the Empire continued the status quo of having a non-Christian official religion.
It was around 10% of the population, more in the cities and in the east but less rurally and in the West.
It was doing okay, but not outstanding.
What it did have was the meme to undermine Religio Roma when it found itself in a position of favor. Basically, 20% would follow whatever faith the emperor followed. Another 30% would give whatever faith the emperor followed serious consideration they wouldn't otherwise if what he was doing seemed to be working.
So, give the empire fifty years of Christian favoritism, you have a large number of people listening and buying in to a doctrine that says, "if you leave you are damned, stay and be saved" which is one of the memes perfectly designed to hit Roman religion at its weakest point and create a new paradigm.
Whatever faith that took over would need simular paradigm busting powers.