Clever idea, but...
...why not make the portal lead to their own worlds distant past? Have them accidentally found their own religion a millenia before its 'actual' start, in another part of the world. It's not unreasonable to assume their cultures knowledge of history is spotty enough to make the past seem like another world entirely.
The PC's could return to their own 'world' only to find
1) A tyrannical, decandent, corrupt church that rules with an iron fist...or
2) A utopia under the auspices of their beloved god, where everyone they knew and loved no longer exists --my fave... or
3) A world where another ethnic group dominates the religion, except for an ancient prophet who bears a stunning resemblance to your cleric...
There's so much you could do with this. Imagine a devout Muslim time traveler who returns from a little time-jaunt only to find no-one knows of Mohammad, but reveres him as the Prophet.
Or maybe the god himself get involved, since the PC's inadvertantly moved up his revelation by 1000 years.
The interdimentional evangelism storyline is nice, wish I thought of it. But a juicy time travel paradox seems to me to be so much more dramatic. By trying to good, the PC's have a direct and possibly catastrophic effect on their homeland/world... Can't beat that in my book