Yeah, I was enjoying the nymph look on the girl too. But then came the cowboy and the octopus(?) and she seem to be out of place, all of the sudden.
I feel a slight lack of cohesion when I look at the character choices. It's like in that game: "which one of these is not an animal?" and then there is a cork lying in the middle of the zoo, except that in this case, each character takes me to one different group of sensations. I think since mine-sweeper is a casual game of sorts, I think a clearer relation between the characters should work better (like you did with the basic themes. Forest, Desert, Sea. Green, Yellowish, Blue. Perfect!).
Suggestions:
A: Fantasy
1. Forest - nymphy girl. Pointy ears, wings, crown of flowers (leaves)
2. Desert - maybe a little red sand daemon. Snake/lizard resemblance, wearing sand-colored rags (Tuareg feel).
3. Sea - a little sea man with fins for ears and fish "lips".
B: Animals
Tons of options! Would look lovely if all looked like your cute octopus.
C: Heroes(or)Villains (couldn't come up with better examples, sorry)
1. Jungle boy (Tarzan style!)/pollution dude(environmental cliché villain)
2. Cowboy/Bank robber
3. Sailor (Popeye!)/Pirate (Har!)

War themed (relates well to mines)
1. Army - leaf camouflage
2. Army - desert camouflage
3. Navy