While there has been a lot of vitriol regarding patch 1.4's changes, most of which I think is vastly overrated in terms of its impact, the protectorates are the one change which I think has genuinely made the game a worse experience.
Right off the bat, they don't serve any purpose that a vassal couldn't do previously. In a perfect world, any tech level would be able to either vassalize OR make a protectorate out of a conquered/released country. Why not give both distinct advantages and disadvantages that the player would have to pick over the other? Instead, we're stuck with an arbitrary and ironclad system that doesn't reflect history very well either.
Furthermore, there's the fact that protectorates are quite possibly the most unbreakable sort of diplomatic relationship in the game. You can't force release protectorates in peace, nor do they ever seem to rebel from their owner's sphere. Instead, you're stuck with a more-or-less unattackable state that neither benefits the owner very much while at the same time being restricted from expansion.
The fact that they can't be annexed is perhaps worst of all, because then you get to experience the constant 'fun' of Russia blocking itself off from expanding eastward because it thought turning every horde into a protectorate was a brilliant idea. Or the equally-likely occurrence of the Ottomans turning all of the Persian hordes into protectorates and not only blocking its eastward expansion, but also completely eliminating the chance of a rival Persia forming.
The fact that colonial nations side with their native protectorates over their overlords is just nothing short of farcical. You'd think Paradox would have caught something this ridiculous in beta testing, considering how much time and effort they spent making and promoting the new colonial mechanics.
In conclusion, either scrap the protectorate system until something workable can be made out of it, or patch the more broken parts of it soon so it at least isn't a gamebreaking 'feature.'