To reach the Hidden Palace from New Kasuto, go into the cave that led you to the area where New Kasuto is hidden. After getting through the cave, go south to the desert. There are three rocks in the southern part. Stand in the middle of the rocks, like this:

  x
x L x

Then play the flute. The Hidden Palace will be revealed. Go inside.

Hit the statue at the entrance to see if it will give you a red magic jar, then go down the elevator.

From the elevator, you can go right if you want a 100 point P-Bag. You will need to cast the Jump spell and avoid some Bubbles.

If you want a 200 point P-Bag, go left from the elevator. In the next room, cast Jump to get over the ledges while avoiding the Bubbles. In the room after that, there is an orange Moa, a couple of blue Stalfos, some Tinsuits, and the P-Bag is below the blocks.

Back at the elevator, go down to the bottom level. You haven't picked up any keys in this dungeon, but that's OK because you got the Magic Key in New Kasuto. Go through the door and watch out for the Wizzrobes and Doomknocker. Use the Jump spell if you want to try to avoid those enemies.

In the next room, there is a blue Iron Knuckle, followed by some gaps. The statue up above might give you a red magic jar. If you fall down the pit in the center of the room, you can get back to this room if you just keep falling until you see the statue on the right side again.

From the room with the statue on the ledge, go right, fighting another blue Iron Knuckle past the locked door.

In the next room there are Wizzrobes along with statues on the wall that spit energy at you.

In the next room you can get a 100 point P-Bag from under the bricks, but you have to deal with a blue Iron Knuckle and some Bubbles.

After that, there is a statue on a pillar and a Stone Warrior guarding an elevator. Don't go down the elevator yet. Instead, go to the right.

An orange Moa flies around while some Wizzrobes attack. After the third statue on the column, there is an invisible gap a couple of squares after the pillar. Jump over it, then break through the wall of bricks. If you fall down the gap, follow the directions below where it says to use Jump and kill the red Iron Knuckle if you want the 200 point P-Bag.

In the next room you will have to fight a Rebonack (Levoknuckle). After doing so, you will get a key and you can unlock the door to the right to get the cross. This item will make invisible enemies become visible. For example, if you take it to Old Kasuto, you can see the Moas flying around that used to be invisible.

Now go back the way that you came, and this time, fall into that invisible gap in the floor. Just walk to the left and you will fall in.

Cast Jump and kill the red Iron Knuckle to the right if you want a 200 point P-Bag. Then go to the left, breaking bricks while fighting Bubbles, a red Iron Knuckle, and avoiding the orange Moa's flames.

In the next room there are blue Stalfos and some Wizzrobes. Unlock the door and take the elevator up. If you fell down here accidentally and didn't get the cross, you can fight the Stone Warrior and head east and try again.

Otherwise, cast the Jump spell and head to the west. When you get to the room with the blue Iron Knuckles and the statue up on the ledge, fall into the gap. Try to aim your fall so that you are close to the right side of the middle block that sits between the two gaps.

If you aimed correctly, you will land on a crumbling bridge. There is a 200 point P-Bag on the left side of the room if you want it. Now fall into the gap again, and if you want another 200 point P-Bag, fall again into a room with Bubbles. The P-Bag is on the left.

Then fall into the gaps again until you get to the room with two crumbling bridges. Jump to the right side of the room and unlock the door. Beyond, there is a blue Iron Knuckle.

In the next room, break the bricks and carefully jump over the lava while avoiding the flying statue heads and Myus. Break the bricks at the far end of the room and you will be in a room with Wizzrobes and a red Iron Knuckle.

In the next room, you have to cast the fairy spell to fly across, avoiding the Bubbles as well as the ceiling drippers.

In the next room, there is a blue Stalfos and an orange Moa and a statue on a pillar. Beyond them, you reach an elevator. If you really want a 200 point P-Bag and red magic jar, you can take the elevator all the way down, then head to the left past a bunch of enemies. In the room with all the bricks, go into the leftmost hole in the bricks and break the bricks on the left side of this hole to reveal either a red Iron Knuckle or red magic jar.

Anyway, back at the elevator, go east through the door and go past the Myu or kill it with a downthrust. In the next room there is another Rebonack. Get the key that it drops, then head east.

There is a gap in this room that you will have to cast Jump to get past. Just drop down to the crumbling bridge and then jump up to the right side. However, the only thing of value on the right side is a 1-Up doll past a blue Iron Knuckle and Bubble. Since this doll is so far out of the way, you might as well take it.

Now you have to drop into the pit on purpose, but as soon as you get to the next room, press start and choose the Fairy spell, then cast it before you fall into the next gap. Now you can float to the right. Avoid the blue Stalfos.

Barba

In the next room, you will fight Barba. This is a dragon that comes out of the lava and spits fireballs at you. You need to cast Jump in order to jump high enough to hit Barba in the face. You should also cast Reflect to get protection against the fireballs. The Shield spell will help, too. Barba will come up from a random lava pit, so be ready to jump over to attack Barba if it doesn't come up from a pit next to you. You can also try stabbing toward a lava pit in case Barba happens to come up from that pit.

Once Barba is dead, go east and unlock the door, then walk past the statue to put the crystal in place, then exit to the right.

This is it! If you did things in order, then you have gone to all of the palaces and put all of the crystals in place. If you press pause, there should be a 0 next to the icon for the crystals at the bottom left. If not, then there is a palace where you didn't put a crystal in place, and you need to do that before making the long journey to the Great Palace. You should also level up until all of your attributes are 8.