Well protectorate and diplomacy (especially diplomace) has always been hard to deal with in regards to the ai in many mods, but in my experience protectorates aren't hard for me to acquire.

In my current Epeiros campaign I managed to make the Getai (who had 5 or 6 cities) my protectorate after I annihilated three of their armies (one 3 quarter stack and 2 half stacks). They offered a ceasefire the next tun but I managed to make them a protectorate after offering them map info and 20,000 mnai.

Bear in mind that this was in a medium/medium campaign and I have yet to finish my current hard/hard campaigns, as I'm a relatively new player, but long time fan, of EB.