Roman society at the time of the emergence of Christianity was actually suffering from a widespread religious vacuum. During the reign of Augustus, which wrapped around the beginning of our era, the Emperor tried desperately to revive traditional Roman religion, much of which had been forgotten or was essentially ignored by his contemporaries. His attempts succeeded largely in politicizing religion - Romans of a century earlier were happy to worship Jove because they revered him; Romans of the first century A.D. were happy to worship Augustus because it scored political points.
Christianity burst into this spiritual vacuum the way that Islam is doing in modern-day Europe. Other cults (such as that of Isis, Cybele, Mithras, etc.) did so as well; over the course of the next four centuries, Christianity defeated all rivals and attained near-monopoly on Roman religious practice.
It is therefore inaccurate to say that the Romans adopted Christianity because their complex religious traditions had grown "tedious" or because they were burdensome. It's more accurate to say that they adopted Christianity because they no longer found their traditional practices meaningful, and had drifted into agnosticism.
Another good analysis, I think. By tedious, I meant that polytheism was no longer relevant to their society. As knowledge grew, it was tough to believe in those oh-so-human deities. So, we're both right, in a way.
Christianity was tailor-made for Rome, and of course, for the rest of Europe, as Rome went a-conquering. A perfect fit.