Yeah, religion should be different from the other things. instead of having catholic and Protestant you could Medieval European or something like that, and then you start with a suitable religion for your choice (Catholic at the start for Med. Europeans, Polytheism for other civs, then they can change it like a government when they get the right tech, wonder or even if they conquer an enemy with it. There also could be missionaries in the diplomacy section, ready to cause disorder unless you convert.
When you choose a civilization, say England, which era is it from? Which peoples are you're peoples? Are they celtic or Roman? Catholic or Protestant, or even Modern? I think each set of civs (the above AND more) should have their own unit, building or wonder. You also should pick at the start you're prefered set, so you can be a different country, but the same base tribe. The choices ought to be limited, though. For instance, the Aztecs can be Meso-American or a catholic country, but none others. 
