I've had the same problem. I dropped back to chieftan level to practise this aspect of the game.
I'm playing a medium-sized pangaea map, 7 total Civs, I established embassies with two of them. With both Russia and China I had ROP agreements that had expired at 20 turns. I wanted to go to war with another Civ and I asked both Russia and China for alliances. Both refused. Then, for 10 or 15 turns, I played as nice as I could to both of these Civs: gave them world maps, territory maps, a luxury, and to China, a city that had culture flipped to me that was Chinese in the first place. Again, I asked for an alliance, no dice. At one point, I offered Russia a technology (engineering, I think), a luxury, world and territory map and 1000 gold (no one other myself had more that 100 gold). Again, still no dice. I gave Russia a ROP agreement and then 3 turns later, I tried again.
What does it take?