The problem with conventional wisdom is that it can blind you to its exceptions. A particular typeface becomes a cliche (which is what "overused" really means) through careless use and abuse. Like any cliche, though, it can still be used in an original and appropriate way to good effect and, like any cliche, it can also be a shorthand to communicate an entire genre, period, or mood.
Trajan, a beautiful face, became so associated with movie (especially horror movie) titles that it has almost no impact in that context any more. But it's still a valuable typeface in many other situations, or even for the right kind of movie (a Roman epic, say).
Nothing destroys a typeface's reputation quite so thoroughly as blundering overuse by clueless, enthusiastic amateurs. That's been the fate of just about any typeface that ships with Mac or Windows or Office (especially the standard weights of Helvetica, Times in any form, Arial, Papyrus, Comic Sans, Apple/Zapf Chancery and the non-OpenType Zapfino). They are all usable in the right context, even Papyrus and Comic Sans, but you have to pick your way carefully and use them very appropriately. The new crop, like Calibri and Segoe, will go the same way in a few years.
Fashion also has a pathological effect on perfectly healthy typefaces. Look back at the history of advertising and signage and you'll see particular faces done to death by designers at different times: Slab Serifs in the 19th Century, Avant Garde Gothic in the 1980s, Futura, currently in vogue for movies. That doesn't mean you can't or shouldn't use them.
So, no, you should not avoid a particular face just because it's been used heavily. But you probably should avoid overused typefaces in the contexts they've been overdone in unless you have a good reason. Don't use Didot or Bodoni for that new glossy fashion mag you're art directing, for example.
Sometimes you have to use the "expected" face just because it's, well, expected. Designers still use Helvetica for a great deal of corporate identity work, not because it's original or even attractive (unless you happen to like Helvetica), but because no other typeface says "corporate reliability" to your average consumer quite so readily. And there are times when "being original" definitely isn't wanted: no movie poster or DVD jacket would be complete without its block of Univers Light Ultracondensed, and you'd be a fool to try something radically different just because you didn't want to be unoriginal.
My advice is always to take each project as a fresh start and treat it as itself. Don't use or avoid particular colors, layouts or typefaces just because they've been used a million times. Use what is right for that project.
