Played 3 games now, and every time I play I get through the initial melee, and then get the "sorry, you don't have the killer..." message. Went through source, and it appears that it will happen every time. If the below is accurate, it looks like as long as you are 'rookie', you won't get a battle.
From BattleArena.xml:
(not arenaRank)
(scrShowPane gScreen "FirstFight")
(= arenaRank 'rookie)
(scrShowPane gScreen "NoMoreMelees")
(= arenaRank 'gladiator)
Are you sure you got enough kills? Was the 50 credit per kill payment working?
Previously, I was able to fight twice to move past the melee battles. Having said that, I think I was paid, but I'm not certain. It definitely counted my kills; I don't remember if I was awarded credits or not.
Need to investigate.
I think this is working properly. You must kill at least 20 ships in 5 melee rounds. If you don't, then you get the NoMoreMelees message.