Oralelk said:
Thanks for all the contributions above. With a few more experiences from recent games, I have added a few contents into the original article. I think I am still missing an excuse, but it is a very rare excuse that I don't see it often.
(1) "Our hands are busy with something else."
This means the AI is either currently at war, or has set out a defined target, and is on its way to declaring a war on the defined target. There is no way to bring back the AI's willingness to take your bribe, unless you either pull them out of the current war, or cancel their definied target somehow. Sometimes, if your military falls behind, this target is very likely yourself!
Just a side note:
You can accurately predict an aggressive AI's attack, from the diplomatic screen. The warmongers are usually willing to take bribes, so you can see at least a few white fonts in the list of "decalre war to". If all of a sudden, all targets are reded out, and you get the excuse of "our hands are busy with something else", then you know you are a little bit late on bribing. In one of my current games, I was attacked by Monty, then Genghis Khan. When I loaded back a few hundred years, I can pinpoint the exact turn where they decided to attack me, and I can go to the previous turn to bribe them to go after somebody else. The lesson here: always bribe them as early as possible.
(2) "We would have nothing to gain."
It is a generalized "lack of hatred" for AIs. Usually, you get this from peace-lovers give you this response even AFTER you become Friendly to them, while they are already less than Cautious to the target. Warmongers also give you this line when their power is significantly below a stronger potential target. Distance to the target MAY be a factor here, as you mentioned. At least, I know distance is a factor of the bribe effectiveness, as distant Civs don't fight really hard, and declare peace very soon.
By the way, I made a little illustrated story on one of my "deity eye and luck games", through the use of map editor and random seeds:
http://forums.civfanatics.com/showthread.php?t=165183
Since I still follow the gameplay in a normal way, all AI patterns here are still valid for a regular game. In this story you can find out various AI bribing examples, so I think it is worthwhile to include it here. (I am not promoting cheating, of course.

)