The first one or two champions I stumble across are normal in price. There's a decent delay between the first one or two champs I see (and hire) and when I find the next few. When this happens...
The wandering champs are level 1.
No hero techs; only one adventure/resource tech researched. In one attempt on this map, I tried to post-correct the bug by researching Recruitment. Didn't change it. I will try researching Recruitment earlier and see if that changes it though on two separate plays (I saved at the very beginning of the game so I have, presumably, a fresh clean set up to work from) I was able to hire one more champ before it happened.
Sovereign charisma is 10.