Despite some of the complaints I have heard, I think that the dungeon is actually a lot of fun. It presents a very different experience than the typical Zelda dungeon. First, the Temple is filled with a curse, so the player is forced to play through the dungeon on a time limit. Furthermore, it is populated with the Phantoms, nigh-invincible sentries who can kill Link in a single hit, draining away his precious time. In order to balance out these challenges, the dungeon has numerous safe zones where the Phantoms can't reach Link and the timer doesn't drain. So, Phantom Hourglass plays like a tense stealth game like Metal Gear inside the Temple. However, another dungeon in the game uses the same curse/safe zone set up, and plays much more like a regular dungeon. It is something else that sets the Temple apart.
In a normal dungeon, once the player clears a puzzle or challenge, he usually never has to clear it again. However, the Temple resets itself every time Link leaves, and thus the player has to go through the entire dungeon over again every time he enters. To many players, this is apparently the most frustrating aspect of the dungeon. However, it is also the greatest strength of the dungeon in my opinion. Even though the dungeon resets every time Link enters, the experience is never the same twice. Ever floor has multiple ways to clear it, depending on what tools Link has at his disposal. Furthermore, there are numerous hidden treasures scattered throughout the Temple to be found by a dedicated player. No other dungeon in the history of the Zelda series has had this many short-cuts, mysteries, and hidden treasures. With the right short-cuts and fore-knowledge, it is possible to clear through the entire Temple in a matter of a few minutes.
However, while I find the dungeon fun, I can't ignore the fact that there are other people who find the dungeon frustrating and annoying. Why is this the case? I have to admit, I always feel a little hesitant to start a Temple expedition. Part of the problem is that the Temple is very large. A dive into the deeper parts of the Temple can take half an hour or more if the player isn't making good time. In a console game, this aspect isn't very uncommon. The Legend of Zelda: Twilight Princess has a 100 floor Cave of Trials after all. However, Phantom Hourglass is a portable game. Portable games should be easy to pick up and play for a few minutes before stopping suddenly. A super-dungeon like the Temple of the Ocean King is too big for that kind of play. Nintendo should have added a better save feature to let players keep their progress between game sessions (or at least a suspend option). More than one mid-point return warp at the very least.
I think that increasing the number of paths, and varying the challenges presented to the player more, would have helped. The strength of the Temple is that it is a dungeon that the player will play through multiple times across the length of the game. Often, floors are limited to the "original hard route" and the "later easy route". Increasing the number of routes, particularly on the most-commonly seen first several floors might have helped.
I am hoping that Nintendo revisits this kind of dungeon in future Zelda games. Preferable console ones.