Well, let's take a look, shall we...
(Spoiler alert: Yes, I know it's been about 30 years since many of these adventures were published, but the following descriptions do give away pertinent details of the referenced modules, on the chance that you haven't read/played them yet.)
1980 - Module Q1: Queen of the Demonweb Pits
Designed by David C. Sutherland and E. Gary Gygax as a tournament dungeon for the Origins '79 game convention, the published edition came out in 1980 and was intended as the final adventure in a series of 7 by E.G.G. (as a sequel the G- and D-series). The "Web" levels of the dungeon feature a series of intricate geometrical interwoven passageways (i.e., "labyrinth") that would make Frank Stella jealous. But before you even get into the pits, the minotaurs show up as WMs in Lolth's Forest. Then, in the pits on Web Level 1, the Gnoll Barracks (3) feature 3 minotaurs. Additionally, spells function differently in the pits and the Druidical spell of reincarnation can actually bring a dead character back as (among other things) a minotaur! (When combined as a single adventure with the rest of GDQ series, this module was voted the single greatest adventure of all time by Dungeon magazine in 2004.)
1981 - Module B2: The Keep on the Borderlands
Again, from good ol' E.G.G. himself comes this classic from the Moldvay red box that introduced so many of us to the original fantasy game. If you're introducing the game to newbies, why shouldn't it have a labyrinth with a minotaur? And if you're trying to bring the classicism of the original myth as well, then of course there should be a direction confusion spell misdirecting the party. Honestly, trying to work your way through this baby as a first-time player seems worse than continuing to type "N, S, W, SW..." and constantly having that damn screen tell you, "You can't go that way!" while playing the Colossal Cave text-based computer adventure. (This module was ranked the 7th greatest adventure of all time by Dungeon Magazine in 2004.)
1982 - Module S4: The Lost Caverns of Tsojcanth
This is another adventure written by E.G.G., and while published in 1982, it was originally a tournament module written for the 1976 WinterCon V gaming convention. In the context of the module, the "Dark Labyrinth" located at the grotto numbered "9" on the "Greater Caverns" map is really more of a magical trap, suddenly appearing in front of the party, closing off the entrance behind them and forcing them through the maze to exit the labyrinth and get back to the main caverns (facing two minotaurs on bullback in the process.) In the context of the rather deep content of the adventure (32 pages of encounters in Book 1, plus 32 pages of new monsters, magic items, spells and pre-gens in Book 2), this is really just a single encounter. If that's a single encounter, what does that say about how deadly this whole adventure is? (This module was ranked the 22nd greatest adventure of all time by Dungeon Magazine in 2004.)
1982 - Module N1: Against the Cult of the Reptile God
Written by Douglas Niles, this novice module was written in four weeks from an existing brief. While it does feature a maze, that maze is occupied by an ogre (not a Minotaur.) The real classic here, though, is that a printing error in an early edition had the maze with NO EXIT! (This module was ranked the 19th greatest adventure of all time by Dungeon Magazine in 2004.)
1983 - Module MSOL2: Maze of the Riddling Minotaur
Finally... an entire module devoted to a maze and a minotaur! This solo module by Jeff Grubb invited players to "Explore the Maze of the Riddling Minotaur in an invisible ink module that you can play by yourself or with a group of adventurers!" Utilizing a seemingly incomplete map and an invisible "A,B,C" choose-your-own-adventure style mechanic, a special pen revealed pre-printed invisible ink to produce the results of encounters as the character(s) worked through a classic "rescue the princess" plotline. Designed for use with Moldvay B/X, the module contained "two" versions of the adventure, 1 for solo play, and an "expanded" version, that essentially just adds wandering monsters to the same maze, as well as a few brief encounters outside of the main solo adventure location for a group storyline.
So let's recap: Over the course of 3 or so years (technically 7 if you include the pre-published/tournie dates), that's 4 TSR modules (out of about two dozen published those same years) that prominently feature mazes and minotaurs (+1 with a maze and an ogre), and 4 of those 5 are in the top 22 adventures of all time.
So what's the verdict?
Well, I think we can say for sure that it is a cliché, but the "most overused one?" Honestly, D&D is wracked with clichés (see the name of the actual game for two of them.) The entire game is founded on clichés (heroes, magic, et al.) But if you're okay with that, so am I.