To elaborate on this topic, see one new player's frustation in this recent thread.
In particular, pay attention to Yargnit's reply #1: "The only way to get yourself to like them enough is to consantly request missions. Basically, request credits, then give hem back in an endless loop. It's way to endlessly compliated, getting them to like you is much easier than getting yourself to like them."
Yes, the "only way... is to constantly request missions..." (my bold).
The relations score that matters is the one that is hard to find (under the Relationship tab [F11], after selecting that player, and hover over your name). Rather than the more intuitive good relations score that you see on the page where you give gifts (feed) or offer missions.
Finally: In reply #13, Vatticson says: "In trinity it was easy for me to have a Diplomacy Victory, but now... its damn hard and impossible!!!!!!!!"
Which echo's my original point.