I feel titles would be a great addition to the heroes update, but as long as PvP was balanced enough that, for example, a "rogue" jumps a "Mage" and although the rogue got the first strike that Mage has enough power to potentially save himself. Titles can't decide a fight no matter the combination of classes in a battle. It should always boil down to skill of the player(s).
I think titles are an awesome idea. I also think titles at different points in leveling as a class would be cool too. For example, level 5 of every class is titled "apprentice", 10 - "novice", 20 - ?, and at max level, training for your class title or an achievement (kill 100 people with an ability from that class) will unlock that final title that sets you apart from all other classes (Warrior Amartin99999). I think the final title should be very difficult to earn, so only the best get the awesome tag. This system would also allow new players to feel a progression not just from experience/level but from prestige along the way.