As noted in the episode "When Aliens Attack", a major religious event occurred in 2443: The second coming of Jesus!
That was probably quite the game-changer, spiritually speaking. Jesus himself was Jewish, is the savior of the Christian faith, and is a prophet of Islam. That puts him in a key position to be able to unite these varied religions into a cohesive (albeit more vague) belief system, even as he was apparently declaring war on Earth's long-since-outdated VHS collections. It seems like a reasonable conjecture that the First Amalgamated Church is what arose from the ashes of all that magnetic tape.
Incidentally, it appears Catholicism didn't join them, they just moved to space instead.