Thanks, guys. Not sure I have any wrong holdings penalties.
I eventually got a few ships after building a shipyard in my capital castle. But it was only a few ships and they took ages to appear. Mostly I relied on my vassals ships which were in much greater numbers and appeared much more quickly (and I don't know why).
I've now achieved my aim of becoming King of Brittany in less than 100 years (did it in 80). Only Nantes is not held by me, so I have 5/6 of the Breton counties, plus Cornwall and Devon to form my second duchy.
The Cornish king made it much easier for me by navally invading me as soon as a declared war on him for Cornwall and Devon. Instead of combining all his men and defending his lands with a single force, he sent two smaller armies into my lands, which I defeated easily in turn with my much bigger army (included mercs). Then I simply popped over the Channel and sieged down his defenceless holdings.
So much for the logical calculating power of the AI...!
Also, the cost of making the King of Brittany title went suddenly from 336 gold to 164 gold, and I have no idea why.