I may suggest, though, that instead of adding an accent color in the way sunandshadow described, you cool down the background, and warm up the foreground (or vice versa, according to scene, feel and taste) just a little?
Just, specifially, to make it obvious what is background and what is foreground. The reasonably plain gradient from red to white isn't doing you any favours in separating a few pieces of information (eg, hills in the background fighting the snow hue, rock in the foreground fighting the middle-ground).

Top set of colors is the color palette I did, bottom set is the original. two blobs in the upper right are snow's shadow drop and the mountains color respectively. I didn't deviate too much, you still want the overall theme to be the same, but I feel something like this would leave more of an impact.

In this case, the darker the shade, the cooler the hue, and the lighter the warmer (with the exception of the snow's shadow, because I wanted that to stay cool). Additionally some changes I might suggest are to pull back on the use of soft gradients. I feel a slightly harder line on the snow's shadow is in order to make it feel a little more like a solid mass and a little less muddy. And in the final version, make sure that rock is a solid color and doesn't have white creeping in around the edges, that was making it hard to distinguish.

I'm personally pretty fond of the light hills, but dark works too of course.

I think the single-color palette is a little too minimalistic; it makes my eyes feel tired because they keep looking for depth or shadows which aren't there. But, obviously that's up to individual taste, you should make what looks good and fun to play to you.

@BagelHero, Thanks a lot for your effort, feedback and help :) If I cool down the background and warm up the foreground, with the snow having to remain white, the contrast between the snowball, the snow and the background will be even lower. This is the main reason why I'm using warm colors.

I'm also not a big fan of the solid specular on the underside of the snow (the part where the rock touches the snow). I feel that the gradient blends in better with the rest of the game's style overall.

With regards to the light hills, I too prefer them over the dark ones, but I'll have to work on them to retain the contrast.

I just didn't understand this sentence, would appreciate if you could elaborate a bit more: "And in the final version, make sure that rock is a solid color and doesn't have white creeping in around the edges, that was making it hard to distinguish."

@sunandshadow, To tell you the truth, the single-color palette and the minimalism it brings to the table was commended by many developers and players, and I find myself liking it a lot. Of course, it's still up for experimentation, but I think I'll stick to it for now.

Well, what about a pattern on the snow (but not the snowball)? Like a tiling snowflake pattern, in a pale pink matching the rest of the colorscheme?

I take you meant some kind of texture? In that case, don't you think that it would take away from the element of minimalism?

Don't take this the wrong way, of course, but I really want to stick to minimalism as I consider it to be an important factor.

If I cool down the background and warm up the foreground, with the snow having to remain white, the contrast between the snowball, the snow and the background will be even lower. This is the main reason why I'm using warm colors.

Having everything being the same amount of warm is causing the foreground, background and middle ground to blend together, though. Warm pops, but when everything's warm, everything is actually neutral. This is what the pictures in my previous post were illustrating (I made the foreground cool, left the middle ground, and made the background warmer). While you don't need to take my specific approach, I don't quite see the logic in keeping a bland straight up and down color palette when one that's slightly warm and cool to each end is an easy way to make the entire scene pop.

As for "And in the final version, make sure that rock is a solid color and doesn't have white creeping in around the edges, that was making it hard to distinguish."...
While I was doing a paintover, in your version the rock has white airbrushed in around the edges. I don't know why, but it's definitely there and it messes with the contrast.

If you're really that intent on making them one shade of red instead of very slightly orange-y/red/very slightly purple-y, though, I'd suggest doing the scenes in greyscale then doing a color wash with an overlay layer set to about 50%. That way you can make sure the values/contrast are definitely right before you add in the color, and you can just focus on that, and it should keep the same contrast. Additionally, it looks almost exactly like the end result you've been getting so far, only with 'perfect' contrast/values. Again, good luck!

Oh sorry, I think I misunderstood you the first time! Firstly, regarding the white edges, they're barely visible as is. It's a 'glitch' or a mistake I made since the current engine supporting the concept art isn't anti-aliased yet.

Secondly, regarding your cool-warmth argument, I think I see what you mean, and I have to say I like your suggestion. Just one thing I tried to change - instead of making the foreground cooler and the background warmer, I inverted them. I left the foreground as is, and changed the color balance for the background to an orange-y hue. What do you think is the effect? Is it better, or worse? I personally like it. Even though it doesn't use the same palette, it's barely visible, and blends in really well, don't you think?

Before:

After:

Also, thanks a lot for your help :)

I take you meant some kind of texture? In that case, don't you think that it would take away from the element of minimalism?

Don't take this the wrong way, of course, but I really want to stick to minimalism as I consider it to be an important factor.

My personal feeling is that it isn't working for my eyes with such severe minimalism. So, I don't think I'll be able to come up with any suggestions for improving it without suggesting it become a bit less minimalistic.

Hmm maybe you see it that way because the scene is rather bland, lacking any other props, having too much rock etc..., which won't be the case in the game. Later on tonight I'll be publishing a blog post explaining why minimalism is so important in this game, and I really think it's important within the game's scope it. Needlessly to say, I will be experimenting with some light texturing (maybe even some very light noise here and there could help in this case) later on.

Thanks a lot for your suggestions sunandshadow, I really value and appreciate them! :)

i think you got the balance just right. It reminds me of the old 'dalmation in snow' illusion. it isnt there until it moves. I think I would like to see this moving and I reckon it will come alive.