@fassFlash - that was unnessecarily rude, how about trying some constructive criticism instead? Like "your work would really be improved by learning about color theory. You can search google for color theory tutorials, it'll make your work look much better."
This is looking fun! I'd be screaming all the way through from falling in holes :D
Colors look fine now. 8-bit-ish so you'll hear no complaints from me :)
Whenever I get stuck for a color palette I seek out the past for inspiration! I'm having a wonderful time learning to use the NES color palette to it's full extent right now. Everything is a learning experience no matter how much you already know!