I've done a little more digging on this, and there are at least 2 hidden factors that impact the AI attitude (there may be others). One is related to the handicap (difficulty level), and the other is specific to each leader.
The handicap adjustments are as shown below.
+2 on Settler
+1 on Chieftain
+0 on Warlord
-1 on Noble, Prince, Monarch, Emperor, Immortal, and Deity
This means that, ignoring the other issues like the leader attitude adjustment, before it will vote for you an AI needs at least a +6 attitude on Settler, +7 on Chieftain, +8 on Warlord, and +9 on any other difficulty.
The leader numbers are as follows. These are from Warlords. I doubt any of these changed from Civ IV Classic, but I didn't check.
+2 for Gandhi
+1 for Asoka, Bismarck, Catherine, Cyrus, Elizabeth, Frederick, Hatshepsut, Mansa Musa, Qin Shi Huang, and Franklin Roosevelt
0 for Alexander, Augustus, Churchill, Hannibal, Huayna Capac, Julius Caesar, Kublai Khan, Louis XIV, Chinese Leader, Peter, Ramesses, Saladin, Victoria, Wang Kon, and Washington
-1 for Brennus, Genghis Khan, Isabella, Mehmed, Montezuma, Napoleon, Ragnar, Shaka, Stalin, and Tokugawa
"Chinese Leader" appears to be Mao. I'm not sure why the XML doesn't use his name directly.
In an extreme case, you could look up the adjustment for each leader in your game to make sure you have enough positives, but I think the easier approach is to simply remember that the worst case scenario is a -1 attitude adjustment. Therefore, as long as you have a +10 on difficulties Normal and above, you should be OK regardless of leader.
One final note. There are a few other factors in the function that I haven't quantified yet, so even the +10 example above isn't 100% accurate. In the absence of things like "warmonger respect" (whatever that is), it's correct, but don't come crying to me if you have a game where some AI with a +10 attitude doesn't vote for you. I told you so.
