i find the best way to get a protectorate,Omanes Alexandrapolites, is to take every settlement but 2 or 1, and then move your armies in around their capitol, then blockade their ports (if any) and tell them youll kill them if they dont accept.

using their capitol to discuss matters seems to get more response, and or talking with the faction leader.

always juice up the deal with the promise of cash... nothing says "I love you" like a chest full of gold!