Also a nice idea is to just give the AI some gold. Now it might seem like a waste, and at the start of your campaign it's a bit hard to do (since you'll be strapped for money), but 5000 or so (which is less then the top buildings you can build at the end) will come a long way. Or make a tribute for 1000-2000 per turn for a while.
If you can spare it, that will get relations up in no-time, while also making sure that whomever you helped gets a good push. It's a good way to sandwich an enemy country. send a diplomat to a country right behind your enemy and try to get an alliance this way, and if you do it right, you'll soon be having borders with your new best friend.