Whenever a scout finishes, all other un-scouted provinces increase in difficulty slightly. This increase is not always enough to cross the threshhold and change the visible difficulty rating (e.g. from Easy to Medium or whatnot) but sometimes it is.
This is part of the game system: the intention is for each province to be slightly harder than the previous so that the difficulty increases gradually and you keep up with it by building up your city. I am guessing that the reason this increase is tied to scouting is to give you some amount of freedom in choosing which provinces to complete in what order.
The part that's confusing to me is that the change in difficulty happens when a scout finishes, not when you start scouting. I always wondered why, since you can't cancel scouting.