First let me say, I like it. It has a cutsy zelda-meets-legoland feel.
You mentioned you had a large palette to work with and frankly, I don't see it. You don't seem to be using any more then a few colors, and in many cases those colors are poorly selected.
For instance the mermaids hair, bright blinding yellow, is barely distinguishable from her skin color making the hairline almost unnoticeable.
Many of the other colors are just too basic and glare out at the viewer. In the mermaid scene the water the bushes the temple all are examples the overuse of basic fluorescent colors. There is nothing to tone down the overly purple tint of the temple, or the dull yellow of the sand or the blue of the water etc.
Looking closer at your work I see you do indeed use many colors, most of which add nothing to the peace, they are hidden beside colors almost identical.