Seems like you're matching the style pretty well. Be aware, though, that sharing colours that the main character uses (the blue and yellow) changes the visual priority of the bird for the player's eyes a little. Maybe pick some other colours for your sprite, like greens or something like that.
Also check out how Nooks did the gun on his. It has a good outline to keep it defined and popped against any background.
Using NES palette, use the brighter colours for sprites, because its likely the darker ones will be used for backgrounds, and you need your sprites to stick out. Also, try being very strict with your colour usage when working with NES. I know the bird doesn't follow NES restrictions, but its pretty close. Try to recycle your colours as much as possible. For instance, the black and grey are completely unnecessary. You can use one colour for the eyes and all the outlines, and another can be used on the gun, the head, and the body.