The red shading marks the region (or regions) you cannot move the currently selected army because of the ZOC (zone of control) the enemy army you share the region with is exerting on you.
You will need a certain amount of military control on a surrounding region to be able to move there when in a enemy ZOC, which can happen because of an enemy army or an enemy fortress is sharing a region with your force.
There is a ZOC icon on the lower right panel. It's tooltip will tell you how strong the ZOC is and what military control you need on a region to be able to enter it.
Bear in mind the ZOC depends of the military control of the surrounding regions, the patrol value of the enemy force and the evasion of your force.
If you detach your cavalry units you probably will see no red region as they are more mobile and can penetrate on enemy territory more easely.
Sometimes leaving wagons and arty behind is enough to escape an enemy force ZOC. That, or sending some other friendly force to get some military contol of the red region.
Here you have a ton of info and numbers about ZOC's in AGEOD gamesviewtopic.php?t=13103
Not that you need to know all that to play, but just in case you like to know all the details.