Ratskinner
Adventurer
Yeah, but then you'd have "melee-based class alpha" in stead of "Fighter" and "melee-based class beta" instead of "Gladiator". I think that would be worse.
"Fighter" seems pretty generic to me... as does "Rogue" (although "Rogue" doesn't necessarily connect to "skillsy-guy" in my head). "Cleric" and "Wizard" have a little more baggage, but "Magic User" seems very vague to me. At the level of sub-classes, there's still plenty of relatively generic terms floating around. Off the top of my head:
Fighter: Heavy Weapon specialist, Defender, Tactician, Archer, Two-Weapon specialist, Weapon Specialist
Rogue: Acrobat, Skulker, Striker, Expert, Face
Cleric: Leader, Invoker, Avenger
Wizard: Blaster, Leader, Controller