As much as people imagine Portugal as "yet another naval European civ" they could have come into G&K with a nice religious boost. There is a story that in one battle against the Moors, a man (who would later found and become first king of Portugal) saw a cross in the sky and begged God...not him, show the Moors, they were the ones that needed it.

You might have to take a leader that doesn't smack you right in the face to get someone known for religion however.
Arabia and Spain are highly connected with religions due to their efforts to spread religion. England and the Netherlands could be just as connected to religion for the same reason as Spain (and perhaps more so because they not only spread Christianity, they both pursued religious changes, leading to...problems with the Catholic Church).
America would have made for an interesting religious civ as well. Depending on how a research is done, America generally ranks from one of the most religious countries in the world to extremely religious for being a rich country with European roots, and early American history certainly would have made room for a religious UA.
Brazil would have been an interesting choice. It was a prime target for the Jesuits and, in fact, a depressing (for any American that might move to Brazil and need to learn about the culture, literature, etc.) amount of Brazilian literature from the colonial times are very religious in nature.
Well, there are a lot of potential sources of religious civs, so long as we can avoid the trap of labeling some as "primitive." The Celts and Maya were strong choices, and I'm a bit surprised that the Aztecs didn't get their UA changed to give faith (in vanilla culture was used for religion as well, just look at the old piety tree).
Ethiopia got a UB, not a UA, associated with faith, and, as far as my limited knowledge goes, that is perfectly logical, even if the time may be a bit off.
Not that there aren't more religious civs out there, but the choices aren't strange. They are pretty darn logical in fact.