The AA in the foreground swords is inadequate. When you're dealing with long "steps" (i.e. a line that's just slightly off vertical/horizontal), the AA has to be longer to match, otherwise it doesn't really help make the edge smooth.

From the http://pixeljoint.com/forum/forum_posts.asp?TID=11299 - PJ Pixel Art Tutorial :

The lightest colour on the mountains is barely distinguishable from the middle one, I think they'd look fine with it gone.

The texture on the ground is both very intese for something that is probably a low-importance element, and has the wrong perspective xP Consider not drawing out the entire ground texture, but rather just suggesting it here and there with spots of texture, and at the edges of shadows and such. If you do that, you'll probably make the entire piece less noisy, and thus be able to add more visual elements safely.

You could make the sky both simpler and more interesting at once by texturing the bands of your gradient instead of or in addition to blending between them. You could suggest fog or clouds, or you could use abstract shapes that improve the mood.

What is the light source?

What sort of things do you want to add? Instead of thinking about adding more details, consider the composition as a whole, what would improve it? I think it could use some large framing foreground elements, and something in the far background and maybe something between the foreground and the current background, to better show the scale. You might also want something lighter in front of the character (or to lighten the mountains, e.g. add some atmospheric perspective haze, or some fog) so that they stand out better, as they currently blend into the dark mass of the mountains a bit.

The towers and moon(?) are rather far off to the side. If they're meant to be important, I'd move them a bit away from the edge. I'd also scoot the character in a little as well. That would keep them from drawing the eye off the image, and help fill in the massive empty gap that is the middle of the image.

If the moon and towers are meant to be connected (I thought they might be due to the shared blue colours), maybe centre the moon on top of the middle tower? The moon could use some AA or reduced contrast between the black and light blue outlines on it.

Not sure if it's part of this, but I found the logo a bit hard to read. I'd move the hook on the T in "GATES" down a bit, so that it doesn't overlap the E and gives the stem of the T enough straight length that the letter is recognizable at a glance.

The animated red texture on the letters is a little dizzying. I think it looks cool, but could stand to be darker so that it doesn't stand out so much. It's not a big problem if it stays as-is though.

The step thicknesses on different letters don't match, which looks odd.

Don't have time for an edit this morning so here are a few examples in a variety of styles:

http://pixeljoint.com/pixelart/120493.htm - http://pixeljoint.com/pixelart/120493.htm

http://pixeljoint.com/pixelart/23563.htm - http://pixeljoint.com/pixelart/23563.htm (on the left)

http://pixeljoint.com/pixelart/53873.htm - http://pixeljoint.com/pixelart/53873.htm (in the background)

http://pixeljoint.com/pixelart/90396.htm - http://pixeljoint.com/pixelart/90396.htm

Notice how in all of these cases, most of the area consists of clusters of solid colours, but there are some details that break them up. The basic idea is that you don't need to draw every single crack, just the bare minimum that the area reads as having cracks.

That'll also help you get away with not calculating the perspective, since all those cracks don't have to be connected in a logical way, cracks of differing sizes due to perspective can just have solid colour between them.