I think it's certainly possible but it depends on the people involved and how fanatically religious they are. I think relationships can work provided both people are willing to be sensitive to the other person's religion and try to keep their relationship somewhat seperate from religion (ie not trying to drag partner to church etc etc)
For example I'm agnostic - I don't really care about other people's religions so long as they respect the fact I don't feel the same way and probably won't anytime soon. This implies them being somewhat open minded, never trying to convert me, not talking for hours on end about how awesome their religion is etc etc etc...
I think some people are more inclined to be intolerant of other religions. Maybe they've been raised from the cradle in a totally one-religion environment and aren't built to cope with other religions. Maybe it's just really important for them to be able to discuss/share their faith with their partner, etc. In my opinion it epends a lot on how into their religion they are - how much they go to church, family influences, personal values and so on. And then of course there might be past influences - maybe one girl might be totally turned off Christians because when he dumped her he said it was because "she was evil" (although in reality he was just a jerk and pulling the religion card because he sucked). *shrug*
I gotta admit though, I'd be sprinting away at top speed if I was in a long term relationship and my partner said "hey honey, I love you but if or when we have kids, they're going to grow up as Christians/Catholics/Jews/Seventh Day Adventists - oh and by the way there's going to be zero further discussion or compromise on this." <--- I think when you run into people like this (and they do exist), you should run, because the relationship is just not going to work :/