I know you asked about colors, but I think a big problem is that everything is cramped, you got a nice set of elements and flow to it, but everything is competing for space and overwhelming the viewer. You've done a lot of the legwork but you were too ambitious and now you cant give up either your screensize or the amount of elements in there,
if you added say a 50 pixels in every direcction you could fit all the things you want there far far more comfortably, as it is there is no negative space to separate anything
Also, dunno about the saturation, sometimes it's ok for cartoony stuff


actually, gave it a try and just 32 pixels horizontally and 8 pixels vertically is already pretty good.
Pixelart is often lauded for the attention to detail, but also remember you can overdo it, if you put too much stuff in there's no priority to anything and it all becomes noise no matter how well you pixel each little thing.
I also got the feeling with the pallete and the design of the character that you have good ideas but you cramp in too much stuff , your tones in the pallete were all shared by too many places to really diferentiate the layers and the sprite had so much going on you couldnt tell anything apart (that's priceless coming out of me, I suck at holding back on that XD). Specially the sillouethe was really hard to tell, it was all just one big square.
I was about to finish the edit before the last step, but I really wanted to bring out the character, so I modified the level a bit and made the color tweaks.
Character: incredibly high contrast and saturation.
foreground: (actual ground) has some contrast, hi saturation but darker, never as bright as the character. note how key elements are dark.
background: far less contrast between castle sky and clouds, they actually had the biggest range and that was really really distracting. Brought the castle color closer to the sky blue for atmospheric perspective (look it up) and the volumes of the castle actually have a bit higher contrast.
Try half closing your eyes and looking at your image blurred. You see the shadows of the mountain, the junk and the castle.
Now try it with my edit. The stairs, the char and the junk stand out because they're what you interact with, as it should be. Actually the stairs ground should stand out a bit less because they're not an obstacle, and the ground should stand out more, could probably fill the top of the floor with highlights and remove the darkest shade from the stairs to get that done.
pallete is ripped to shit tho, probably a lot of redundant stuff and I completely changed your character but hopefully I make a point.
EDIT: updated the character a bit and that shitty ledge I made for him is bugging the hell out of me...but I already spent waaay too long on this so I hope I dont fix it Xp

couldnt help myself. atleast the grass is just scribbles :p
Also, totally balls out nasty version of your char

Look at him! I love him, he's such a dirty asshole. the dick.
it's something I know you didnt pixel but I saw inbetween the pixels. Thanks for reminding me that's why I love pixels =)
might wanna use that face for SOMETHING, if ya dont mind :p