A Roman discovery and successful colonization of the Americas would butterfly Columbus away, and I'm having trouble seeing them falling out of contact pre-Constantine (although we can perhaps grant that they break with the Christian Empire afterwards if you're dead set on keeping them pagan)--the fall of the Western Empire in the 5th century seems like a more natural time for something like that to occur.
Assuming, however, that the Romans did successfully colonize America and subsequently lose contact with their American colonies prior to the Dark Ages, and that this did not significantly alter anything in the Old World, and that permanent contact was not reestablished until c. 1492...
If it didn't have to deal with the Dark Ages, how advanced could the colony have become by 1492 when Columbus makes his voyage?
Hard to say. The colony will, at first, be much smaller than Rome, and this size will prove limiting for a few centuries at least, until they've brought enough of the continent up to "modern" tech levels to do amounts of research comparable to medieval Europe. They might be on par with Europe, but probably not significantly ahead, and likely significantly behind in some areas (in particular, they will probably lack gunpowder, although they will probably learn that from the Europeans soon enough).
How would the American Empire react to Columbus?
"Oh look, an emissary from our sundered eastern cousins." Indeed, TTL's equivalent to Columbus may well have explicitly set out with the intent of making contact with the fabled lands on the other side of the Atlantic, and trading with/converting them. Assuming there is an American Empire, of course--it is entirely conceivable that the civilization founded by this colony would have fractured into multiple polities, to say nothing of the Native American states Romanized to varying degrees elsewhere on the continent.
How would it interact with Europe?
Well, trade, of course. Europe would try and convert them, if the Americas have developed a proselytizing religion or two of their own they might try to convert Europe. I imagine the Roman and Roman-influenced states of eastern North America might find gunpowder useful in fending off the horse nomads of the prairies. European colonization of at least parts of the Americas will probably still occur, but with the native populations having already been innoculated against European diseases and being significantly more technologically advanced, it'll probably look more like the OTL colonization of Asia than what happened in the Americas.
I don't think that a roman empire that has Conqured everything from Canada to Venezuela would be to hard to imagine. If the colony is established near the end of Augustus reign say 10 A.d. It has 1482 years to expand
It has also had 1482 years to break apart and for indigenous states to adopt their technologies and become too formidable to conquer and/or hang on to. Remember, 1482 years after the original Rome was established, the empire in the West had collapsed and the empire in the East consisted primarily of Anatolia, Thrace, and various bits of Greece and Italy. An unchallenged Rome reigning over everything between Caracas and Anchorage is both boring and unlikely.