@liv, if you look at your "diplomacy" screen, hit the button that tells you about your relationship with the opponent. Down the bottom of that sidebar there's a list of reasons why the AI likes or dislikes you. Same religion is one of the positive multipliers - with some conditions though. If you have converted their Holy City then you cop a penalty for that, even if you are both following the same religion. The best way obviously is to convert them before they gain a religion, but that takes a fair bit of planning.
This is another case of different rules for the AI and human. AI takes no penalty for converting your holy cities on that diplomatic screen.