Really? I can honestly say I've never managed to do that - hence my sense that at RD everyone simply goes mad (with some reason and empirical evidence). It would make total war a little less total if I could setup vassal buffer states... Did you have to do anything other than be friendly/allied for a long time? i.e. bribe them every turn? I must return to the Dojo and focus on my lessons.
I think in R2 the system struggles when there aren't many indicators racking up on either side (be it like/dislike), as the AI can be quite complacent. In some cases you might be able to sweaten a deal (the initial one most importantly perhaps - to get the "likes" ratcheting up) with a bribe but it's fair to say that unless you follow the progression of agreements that Slaists mentions, the AI won't be interested.
Starting relationships off seems the hardest part in R2. I'd say it's also rare that erstwhile enemies become friends/allies. Often the easiest way to be start building a friendly relationship with a faction is to have mutual enemies, declaring war (as a diplomatic measure alone!) is always possible: no one can say "no".
I'd say you'll always have factions miles away who are disinterested in you and maybe minor factions with not much to trade too. Generaly, a large AI faction (with trade resources) will be happy to trade once you are friendly enough.
Bookmarks