It also happens for any of the other "get a province in region X" missions. It's absolutely ridiculous. You could have just two provinces in the region, and even though there are dozens of other perfectly good provinces they could conquer, (even available uncolonized land in some cases) they will still go hostile to you and desire your provinces. Even if you are allies. The AI really needs to be programmed to desire the easiest possible land in the region. Such as uncolonized land or a weak non-western minor. At the least, make it so they don't desire allies' provinces unless there are no other options. Going hostile to every single nation that owns land in the region is just ridiculous. And the gameplay effects are quite serious since it constantly destroys perfectly good alliances for no logical reason.