From the in-game news:
Mercenaries Issue Fixed 2010-06-
30 14:47:38
Due to Team oversight with the mercenaries' logic, the latter could pass into the next Tier without having the necessary levels.
As of today the mercenaries must have the necessary level, just like the heroes, in order to be upgraded into the next Tier.
All the mercenaries who don't have the required level will be demoted into their real Tier.Mercenaries equipped with higher Tier items will be able to keep them. If you choose to remove such equipment from your mercenaries you won't be able to put it back until your mercenary meets the requirements.
Sad but there is no bug... as for gold you spend to upgrade them