The number of provinces you have is different than how strong your dominion is. The "vanquished" message indicates that your dominion has faltered, which is an instant game-over.
Keep an eye on those candles. They measure how fervently you are worshipped by the people within the individual provinces. If there isn't a single white candle left burning, you'll lose the game, as there is nobody left who really believes in your pretender's divine nature.
Be sure to design pretenders with a fair amount of dominion strength (5-6 is good for starters). That'll affect how fast you spread your faith and make it easier to avoid such a fate.
Even more importantly, be sure to appoint a prophet. (Select a commander and choose the appropriate command from his/her/it's menu.) The prophet, much like the pretender him/her/itself, spreads dominion automatically. That can be a vital early boost, plus the prophet also gains some nice clerical powers. In Dominions, that means some nice spells for the battlefield.
You can also build priests and set them to spread dominion. Having them build temples is also important, albeit costly.
Last word: if it seems unfair to have to juggle this aspect of things, remember that your enemies have exactly the same issue to deal with. Often, you can avoid costly battles in an enemy's home province by simply preaching their dominion down to zero and vanquishing them that way.