Do that some more, and see if you can make the supply costs increase farther .Sounds like a likely cause.
Did some experimenting. Seems that the supply increases by 1 anytime I move my army outside of my borders. If the army is brought inside my borders the supply cost will decrease by the number of units needing supply but will still remain even though there are no units outside my borders. If I take the army outside again, the supply increases by the number of units needing supply and 1 is added for every plot I move the army. (Does not matter which direction I move them either) This begins shortly after promoting my axeman to Captain. It seems to happen anytime I move a unit with the enlisted promotion outside my borders. (Tried some units without it, nothing happenned, anytime I moved a unit with the enlisted promotion though, the supply cost increased by 2)