What?! Dude, religion brought more dynamic relations to civ. I belong to those who think that removing religion is a step backwards.
Dynamic isn't always a good thing. If you completely randomized all relations every round, it would be super-dynamic, but wouldn't make for a very good game at all.
The diplomatic problem with the religious mechanics (there were lots of other problems) was that it prevented the AI from making decisions about who their friends and enemies were in the same manner the human player could.
A human player doesn't care what religion another country is - so why should the AI? Unless a human is so far ahead he can afford to do whatever he likes, he makes his decision based on things like who's got stuff he wants to trade for, their relative level of power and threat, who their enemies are, and so on. For the AI, religion threw a monkeywrench into the diplomatic planning, effectively ensuring that the AI couldn't really plan out any sort of diplomatic strategy because they were stuck with whatever choices religion made for them. This was a burden the human didn't have, and made for an unnecessarily crippled AI.
One of the key goals stated for Civ V is to have an AI that makes sensible decisions about diplomacy - calculated decisions that work to the AI's benefit, in the manner that human players make their decisions.
In theory religion was a neat idea, but in practice - at least with the system that we have in civ4 - it doesn't really work. Religions being founded by a technology; Buddhist Vikings; bad diplomacy; very limited set of choices only reflecting modern religion; and so on. It had to either be vastly improved and reworked, or scrapped altogether. With all the other changes being introduced, they decided for the latter.
I suspect it will reappear in an expansion, when they have more time to focus on devising a workable system for religion. If they do, they'll probably be gathering ideas for it here, so if you want religion back the best thing to do is acknowledge the problems it had and come up with new systems that offer solutions.
As to the whole "step back" notion in general, each edition of civ adds some things, so there are only two words I have to say: feature creep.