I think that a cliched character isn't that big of a deal, so long as it's plausible. Warrior son of guards from Stromgarde? Great. Hate undead because the Scourge destroyed your family? Statistically speaking, there are going to be a lot of those people. And I think that roleplaying is a lot more fun when some people do play the 'establishment,' the average Joe that fits in when people make generalities like 'Night Elves hate orcs because of deforestation' or 'Tauren revere nature.'

Having a rather anonymous 'starting place' for your character gets a large portion of backstory out of the way, and makes sure that said backstory actually fits within the lore. It's always better to be a vengeful paladin from Stratholme, as cliched as that is (with apologies to the person I know that fits that billing) than to be a princess from a secret tribe of humans that lived in the Badlands or something. It also provides a nice contrast with all of the people that are so determined to be different.

The key is making sure that your character is unique in all that. There're going to be countless other refugees from Gnomeregan, but it's your personality and quirks that define you. Make it about how you were abroad making a business deal when things went under, not how you escaped Thermaplugg's personal clutches because of a magical talisman you inherited as a descendant of the ancient kings and queens of Gnomeregan.