Well, neither did the Aztecs or the aboriginal Australians, but that didn't shock the foundation of Christianity. The "good news" (to borrow a Christian term) did reach them when time was due. I would think that the same would apply to alien life forms. And about the fact that the Colonials are polytheistic, well, I suppose that they would deal with it like they do now with people of different religion (or no religion). A lot of Bible thumping and bell ringing at Sunday morning.