Give him some bug mandibles on his face or something that really alters his silohuette/form and think of another way to color him, perhaps like a penguin?
And Phlakes was right about pixel size / resolution vs. another medium. This simple of a character could easily be represented with only a few pixels (relatively speaking) and, really, if you're working properly with the pixels and defining your silhouette first in illustrations like this one, you can get a pretty near-infinite resolution with your pixels if you cluster the colors properly. This is obviously only an illusion since your resolution is predetermined by your canvas size, but your skill in pixel placement and clustering can easily hide this jaggedness and can mimic cel-shaded graphics and animation pretty faithfully, even at very low resolutions.
The key to determining what resolution/canvas size to use is determining how 'fat' of a pixel you're comfortable working with, and whether this pixel size meets your idea of the style of graphics you want. The 'fatness' of a pixel just means how big do you want a single pixel to be relative to the level of detail you need in your graphics, and the larger this pixel is, the more symbolic you have to be in your representation of detail (i.e. the flame in your 'sprite' above would only need 3-5 pixels to represent the lightest yellow color in it in, say, a 32x64 sprite version, meaning you can't use much of it and your colors would need to 'cluster' more to represent the bright in that portion of your sprite, thus no fine-grain detail as you have in your flames atm, which isn't needed anyway, since simplicity and clarity tend to go hand in hand.)
