It's not completely unheard of, though. Think about how many times Rev. Jesse Jackson has run for president. The larger problem is the mistrust that some people have for people that aren't "mainstream" Christian; and even then it depends on what they consider "mainstream." I don't know if the Bishop thing will work against him, but if it does then it won't be because he's a religious leader but specifically because he's a Mormon religious leader. They'll try to get people to think that he's going to use the Presidency to push some shady Mormon agenda or to give Mormon leaders undue influence in Washington. (Similar things were said about Kennedy because he was Catholic, and he wasn't even a religious leader; people claimed that if he was elected then the Pope would gain control over the US government.)
Hell, with Obama they even did double duty. Claimed he was going to give the Muslim Brotherhood power over the United States AND had a huge scandal concerning the preacher of the church he attended for 20 years or so. People always say crazy things when it comes to religion.