I have the same "Happy Anniversary" edition of Dungeon Lords and can only find one cube of each colour for the evil-o-meter. So unless I suspect in your case its just a minor packing error and you have 4 extra cubes.
As @Samthere said, the word new is to clarify they are refering to the character that is in the first position after the first effect of the card.
Anyway, let's go to the rulebook, page 17, Paladins:
The paladin is a special adventurer that is always at the front of
the party. Any new warrior will push ahead of everyone but
So the ...