as i understand it, once you attack a recruitable hero, you will be unable to hire any heros from that point on, they will simply refuse to work for you, the ones you have you get to keep, but future ones are blocked. i usually restart/restore when this happens though.
as to why it happens, for me it seems to occur when i have a unit in a town selected and either try to use him to recruit the champion, or click near the champion and the game screws up and decides I clicked on him instead. instead of recruiting the champion, the selected unit comes out and attacks, and i get screwed. i've also seen it where the unit i have selected isn't really registered as selected, i.e. i can move him, but its showing me options as if a city were selected, then my orders cause really bizare behavior, its usually after an end turn.
if they are actually attacking and you are getting that message, i don't know what to say, maybe you had a unit with a destination and a champion moved into it causing an attack? maybe a bug with autoexplore or just an undocumented feature from one of the hot fixes.