Actually, I'd say the randomness of acquiring religions was the biggest problem with Civ4 religion. However, *both* issues are very easily solvable. In Civ5, we know that City-States have a rapid decay in influence, meaning you have to keep working hard to maintain relations with them. I've seen no proof yet, but I'm guessing major AI civs are similar. So there is a very simple fix to the Religion-Diplomacy problem, make the immediate benefits of adopting a Civ's state religion relatively large (a +3 to +4), but have it decay relatively quickly, so that only frequent maintenance of that religion in your cities will allow you to retain the diplomatic benefits of having the same State Religion (so you have to actively spread the religion to as many of your cities as possible, & build all the available religious buildings, in order to retain the maximum diplomatic bonus-this works even better if a neglected religion ultimately disappears from a city). The flip-side of this is to have the initial benefit of adopting a Civ's State religion small, but have it grow *only* if you actively spread the religion to all your cities (but still have the relatively rapid decay, so you really have to *work* for the maximum diplomatic bonus). Of course, your religious settings should play as much-if not more-of a role in religious diplomacy than whether you have the State Religion or not! Another suggestion that's been posted around here-& which is excellent IMO-is to take Religions out of the hands of the major Civs, & instead tie them to certain City-States, again negating many of the problems with Civ4 religion.
So, you can see at least 4 ways in which Civ4 religion could have been adapted to work with the Diplomacy system of Civ5. I simply can't believe that they couldn't get *any* of these systems to work in the game. Instead, I suspect they tried to shoe-horn Civ4 religion into the game-unchanged-then abandoned it when it didn't work. I'd like to be wrong, but it just doesn't feel like I am!
Aussie.