So far, the only times I have been able to gain a Protectorate has been through the "Accept or we will attack" option. Germania accepted right off, while Brittania countered with a demand that I pay them 16k per turn for 3 turns and give them back three provinces I had taken. I refused. Everyone else I have tried has refused outright, but I never gave them the ultimatum either. The very next time I spoke with Germania via emissary, they broke it off.