I found out too late that giving them your map as a present or little bits of money improve the relations. Also don't execute the prisoners of the nation or they will be unhappy too. I also had a pretty decent alliance with the english break, but I was asking for it with the Papal war and stuff. I think it should be a little easier to improve your reputation. Everyone hates me now.