I've found (on Emperor/Immortal) that the AI will most often be afraid of me after an early warrior rush or similar - it doesn't seem to happen late game, when they've already got good reason to hate you, but early on, if you rush an enemy AI and kill them quickly, other AI might become afraid.
I had Darius be afraid of me in one game, briefly, though he quickly turned hostile instead, and that was after I' rushed the Iroquois. Similar situation with Suleiman after I killed Montezuma in another game with Chinese warrior rush. I imagine that, before they get the opportunity to become super powerful, such a display of force is supposed to be frightening (and technically should later on, but won't because they'll have built up too much to consider you a threat)
Don't know what it does though. They certainly weren't afraid enough to give me freebies, and weren't too afraid to enter war with me a little later, so who knows? Hopefully the patch will let us in on it