It's ai problem not map, but as you have to put the new provinces in the ai files, maybe it could be solved (or not)
For example, on your test games, does Bulgaria protect the Aegean coast?
Well you could do this in your own game?
Go to the db/misc.txt file, near the bottom, turn on the AI spy.
Run your game to where you wish the ai to do its stuff for Bulgaria.
Stop the game, open the list of current ai files that are running. See the bulgaria.ai file or similar?
Open up that file, and add the provinces you wish to protect into the province priorities = {
and test it yourself?