I like him a lot! The only significant problem I see is the lack of contrast between the black and the dark green, which is also to far from the "bright" color. Although the red is not bright in itself, the general color balance has the mid shade too close to the black. Are you on a fixed pallette like NES or GBC? If not I would suggest less saturation to bring the colors closer together, and then set more natural ramp, like a warmer, a bit lighter green for the mid shade, and a more orange-ish red.
I think he is more like a two 16x16 tiles tall creature than a 32x32 object, as that would be the size of its collison mask in game, the wings would just be overflow.