Have you noticed that it's possible to have someone like you enough for a cease fire, alliance, or pact, but for some reason the option is still grayed out? That happens because you have an independent opinion of the other player as well. This is unlikely to happen with an AI because they probably send out many more envoys than you do, but it's quite easy to observe if you play against another human player.

Example: You decide to play a 4 person FFA with one friend and 2 AIs. You and and your friend may decide "hey, let's ally, share vision, and get the jump on these guys!" However, if you haven't been improving relations (as you would with envoys), then you will not be able to ally with Bill. In fact, it's likely that the AIs will ally with each other before you, if you ignore envoys entirely.

Think of it as your people's opinion of that player. If your people don't like the other player, you won't be allowed to ally with them.

I've explained this to a few of my friends. Some think a very interesting addition to the game. Others (usually the guys who would get an advantage by "allying" with everybody), feel it's an unnecessary hindrance as it doesn't promote the same level of backstabbing. Personally, I like it.