Skyshrine is a tough zone to find anything in. The maze itself is easy, it's getting TO the maze that's hard to find. Just did it myself a few times to make sure I can lead my friend who looted the tunic I'm getting (to MQ, I helped kill on my cleric, but tunic for my druid) to the quest npc's.
From when you ported in via Cobalt Scar :
Go around the pool in front of you and open the door. Take the first Right. Then take a Left corridor in the middle of the room. Take your next Left and follow around. Open the gate. Take the stairs to your left. Open the gate. Go up the ramp, take a left and turn left up and around to the Counts. Go around and open two big gates. Take a Right going past Xalamesh. Go up the ramp and take a right and use the telepad. Keep going UP the ramps. Go past Huren Kor'Va and left past Yeinn. Go through the fake wall. Go around the lil pool (don't fall in!). Go through the other fake wall. And you're at the beginning of the maze.
Now your map should have red cheat lines (hehe) that you'll want to follow to the telepads through the maze. Couple notes: When you teleport to the top of the map, go across the hall and then turn back around and use the same telepad you came though. When you port to the right side of the map, you'll also need to turn around to see the telepad you're supposed to use next.
Open the big gate and click on the globe until it lets you in. The first door on the left have the Quest NPCs you need. Hail them and find the one that seeks your class. Do your turn ins and enjoy your new armor! :)