I just saw the word co-religionist used in a Jewschool post, and it seemed so anachronistic. Don't get me wrong, I love the word, but it brings to mind post-WWII era arguments about race and religion. Just like referring to someone as a "member of the tribe." Oh wait, I do that too.
According to the OED a correligionist is: "An adherent of the same religion;" the first documented use of the word was in 1842.