After I sold Labyrinth I wanted to play it. Luckily I had another cart that my colleague has flashed with English text so I can play it. Thank you!
From what I can tell, the game would have been playable in Japanese too, but I don't want to risk that. I think it is useful to get those small hints. For example you will be told you need to get the key and the coin. If you don't know that, it will be very difficult. That's not the game's fault.
I always wondered why the game was only released in Japan. Maybe it had to do with rights to the movie and soundtrack. Also wonder why the game is not more popular. I think many people have bad taste in game, or they prefer nostalgic games from their childhood.
Anyways, the game is based on the movie of the same name. I saw it around 10 years ago, but I don't think it was popular over here. It is an interesting film with Jennifer Connelly and David Bowie.
The game is called Labyrinth for a reason. It can be pretty tricky. I think you will always made good progress, once you understand how it works. I will make a short explanation.
You start the game and after looking around you enter the main gate. From there you will be able to enter a building of some kind. Moving north you get to a grass place, which is the center of the game. In the middle of this place is a Wise Man. He will tell you how to get to the next level. There are four ways to exit the place with the Wise Man: North (up), East (right), South (down) and West (left). He will say for example "Go West for 1", that means you will go to level 1 if you exit left.
On each level you must take a key and a coin. The key is required for the next level. You can take the coin later, but you still must take all coins before you can enter the castle and rescue your brother. The two items are hidden somewhere on the level.
You can find other items to help you, or you can buy them from a guy that appears sometimes.
You can also find hearts. When you give one of your helpers three hearts, you can summon him and then you control both players at the same time. Press B to make your helper stop walking. I have a photo of me and my helper in the picture above.
There are 12 levels and 12 keys. I got a couple of them before I had to quit for the day. Actually I got Game Over. The game has no continues so I will start over some other day.
The main difficulty is in finding the right way through the labyrinth. If you don't find it, you will drain your time which is your life. If enemies hit you, you lose time. If you walk around alot, you will get hit alot. You can buy time from the Wise Man or use the Book item, but you still must avoid getting hit and you must try and find the right way. When you have played a level once, you'll complete it much faster the next time.
I think it is a fun game and no manual is required other than what is explained on this page. I played a couple of hours without any guide, and think I could beat it if I have enough time. It should be mentioned that the game may seem unfair. You can warp from one stair to another, but if you go back, you may warp to a third place. But there is always a way.
Update 2013-02-19: Game beaten. I took some help from strategywiki on the last levels, but I am happy I did. The game took around 1:30 hours to beat, including breaks, mistakes, looking in the guide and other things.