My (limited) understanding of history has led me to the conclusion that there is usually a cultural or economic drive for major social changes. The Roman Empire was a military and cultural power (even in decline) that dramatically exceeded the influence of Jewish and nascent Christian societies - and yet somehow in the span of a few hundred years the Romans converted from a religion that essentially was rooted in Ancient Greek times (thousand+ years old) to Christianity.
Usually when a like conversion is undertaken, it seems like its done because the culture/economy of the adoptee is inferior to the culture/economy of the adopted religion's society. eg: native cultures with relatively lesser technology adopting Catholicism in the 20th century.
What motivated the Romans to abandon Old Gods for the New?
There is so much to this question that answering it is normally a semester-long class. There are, as you can imagine, a number of factors at play. I will identify a few of them for your consideration and offer some suggestions for further reading.
The conversion of Emperor Constantine (312 AD). I have put this at the top of the list not because it came first or was the deciding factor (in some ways, Constantine's conversion was a symptom and not a cause of Christianity's spread throughout the empire) but because it is a single and significant turning point. Before the conversion of Constantine and his subsequent legalizing of Christianity with the Edict of Milan (313 AD), Christianity had never enjoyed state recognition. Contrary to many narratives, this did not always mean they were persecuted, either by the state or other groups. Still, Christianity had never held official status, as opposed to the Judaism, which was a legal religion due to its being sufficiently ancient (things being old was a big deal, as your question implicitly notices). Christianity would not become the state religion of the Empire until Theodosius I issued the Edict of Thessalonica in 380 AD, but legality did a great deal. For the first time, a church could be built publicly, for example (before this time, Christians often worshiped in house churches or cemeteries). What's more, under Constantine the church began to receive a great deal of favor from the state, e.g. bishops came to hold important magisterial power in the empire, money was given by the state to build and furnish lavish churches in city centers. For the first time, the church became a major avenue for career advancement. Consider for example Ambrose (340-387 AD), who was the governor of an Italian province before he became the bishop of Milan--this would have been inconceivable before the legality of Christianity.
Intellectual Connections to Platonism. Your question wondered how something new could supplant something old in this culture, and that is a good idea to consider. You create a strong distinction between Greek religion as ancient and Christianity as new. But let's consider more of what goes into a religion. Thinking about Christianity's intellectual appeal, your distinction between it and Greek traditions starts to break down. Recall that the sacred texts of Christianity were written in Greek; this is not an association that ends with the language. While it is difficult to track the growth of Christianity and even more thorny to identify which communities found it most initially appealing, from the onset, its thought and literature were shaped by Hellenistic influences. Some of this may have found its way initially from Hellenistic Jews who found the movement appealing, but again this is difficult to say (it is indeed a hotly debated topic methodologically how we distinguish Jews and Christians in the first few centuries of the latter's existence). By the second century AD, there was a strong tradition of Christian Platonism, particularly in the Alexandrian school with Origen of Alexandria (a great example is the fourth book of his On First Principles). For an example of how Platonism became a major interpretive lens for many Christian thinkers, consider Augustine of Hippo. In his Literal Commentary on Genesis, Augustine argues that the six days of creation are not meant to indicate that God acted successively over the course of several days, for God must have created the world instantaneously (Bk XII, Ch 4, 33). Augustine's concern about God acting in time is a very Platonic one, as there exists a great deal of distance in Platonic thought between the ultimate One that is God and the created world. For Augustine, God creates the entire world first in his mind, a fitting notion for a Platonist, for whom the spiritual and mental is of a higher order than the physical one. This is one example of how the emerging intellectual culture in Christianity was very much in conversation with the dominant philosophies of the time. This may make it easier to understand why Christianity was not considered a new thing but something very old. The other contributing factor was Christianity's connection with Judaism, which the Romans considered to be an ancient and therefore respectable religion. While there were early Christian voices who attempted to separate strongly from any association with Judaism (the poster-child for this is Marcion, who went so far as to teach that the God of the Jews was a demiurge or lesser deity to the God of Jesus Christ), it quickly became orthodox that Jesus was the fulfillment of promises from Jewish scriptures. This also gave Christianity an ancientness it might not appear to us to have.
Martyrdom. This last point is somewhat controversial, but it bears consideration if only because it has dominated much thinking about this period historically. Within Christianity itself, the traditional narrative is that martyrdom was a major vehicle for persuading others to the Christian message. That Christians were willing and able to suffer torture and death before renouncing their faith, and what's more, to suffer with grace and dignity, moved people deeply and demonstrated the truth of their convictions. This period is filled with accounts of Christian martyrs and alleged conversions of onlookers attributed to their deaths; often, it is their tormentors who are most moved to convert. One should not take these accounts as pieces of journalistic investigation; indeed, the goal of a story like these was not to be historical, at least in the way we understand it. Still, their mythological aspects do not prevent us from gleaning some insight from them. We should be willing to consider that persecution of Christianity had the opposite effect from what was intended, doing instead a great deal for its growth. Good examples of the genre are "The Martyrdom of Polycarp", "The Martyrdom of Perpetua and Felicity", and "The Martyrs of Lyons".
There are three points of consideration; there are others that are important but which others may want to contribute. I tried to touch on some of the social, cultural, political and religious elements to give you an idea of how this could have plausibly happened.
Sources / Further Reading:
The Rise of Western Christianity by Peter Brown (Blackwell, 1996). The classic survey of the period, though by no means the only one.
History of the World Christian Movement, vol. I by Dale Irvin and Scott Sunquist (Orbis, 2001). Another survey, longer in scope, covering more than just Rome, but still worthwhile.
Christianity: The First Three Thousand Years by Diarmaid MacCulloch (Penguin, 2009). The largest of the three surveys, MacCulloch's probably ties Irvin/Sunquist's in terms of readability. Expansive and well-researched, it is the least traditional of the three in terms of what it emphasizes about Christianity's spread.
Readings in World Christian History, Vol. I ed. John W. Coakley and Andrea Sterk (Orbis, 2012). A reader of early Christian documents, it contains a number of the martyr stories I mentioned.
The Spirit of Early Christian Thought by Robert Louis Wilkins (Yale, 2003). Discusses many of the intellectual figures and trends in early Christianity.
The Christians as the Romans Saw Them by Robert Louis Wilkins (Yale, 1984). This is a particularly good volume if you want to understand what Christianity looked like to Romans, as it is a careful examination of primary sources where non-Christian Romans discuss Christianity.