There is a difference physically. A maze is a complex branching (multicursal) puzzle that includes choices of path and direction, may have multiple entrances and exits, and dead ends. A labyrinth is unicursal i.e. has only a single, non-branching path, which leads to the center then back out the same way, with only one entry/exit point. The labyrinth is easier.
labyrinth vs. maze
The word labyrinth carries a connotation of being impossible to get out of, unsolvable. This is because of its origin in Greek mythology; it was a complex maze constructed for King Minos in Crete by Daedalus to contain the Minotaur. If I remember it correctly, the Minotaur was an offspring of King Minos, who loved his 'son', even though he required some unsavory feeding practices (he ate people, specifically young Athenians). To prevent the Minotaur from ever finding his way out, or the Athenian sacrifices from escaping, he hired the best minds to design increasingly complex labyrinths, culminating in the last one built by Daedalus. The myth has two branches, one involving the escape from imprisonment of Daedalus and his son, Icarus, and the other, the death of the Minotaur at the hands of Theseus, who, at Minos' daughter's urging, used a clewe (ball) of string to act as a trail to find his way out after having killed the beast. (It's from this clewe that we derived our word, clue, something used to solve a puzzle.)
Mamet, like one of his characters, invents a labyrinthine, convoluted spiel leading nowhere, and like a magician distracts us with his words while elaborately not producing a rabbit from his hat. - Roget Ebert, re. American Buffalo
A maze, on the other hand, is just difficult, complex.
The city is beautiful in all its chipped, unvarnished glory, but their house is located amid a maze of narrow laneways.