Hmmm i got the Brutties as my protectrate now...

It would seem so far that factions are very unlikely to accept becomming a protectrate if they have no where else to go ... as you you are their only adversary, which might explain why those 1 province factions never seem to accept.. because u have them completely surronded...

Also repeated threat seem to work... you ask and threaten them a repeatedly every turn for several turn while keep making moves on them seem to up ur chances.

Also if they dont give u the freedom speech then they aer probably on the verge of accepting.