I had always considered them to be same (like many people do) but realized that they are different in important ways.
In the Book "A Whole New Mind", Daniel Pink explains the difference between the two.
- Maze engage the left brain (Logical) as a puzzle to solve, while Labyrinth is a "moving Meditation" and thus "frees" the right brain.
- Objective of the maze is to escape, while Labyrinth are spiral walking course
- There are about 4000 public and private labyrinths in the United States
- labyrinths are showing up in hospitals and medical facilities
If you are interested to know more, this page has quite detailed explanation of the differences.