Whoops, I should really read more. Sorry 'bout that. You definitely got the look down though. :]
Right now he seems a tad bland, maybe give him something on his shirt or use a different kind of color scheme. A helmet perhaps? If you really don't mind how it looks now, the character looks nice, he's fine for a game.
Made a few versions of my own. (Using the great NES palette Blob posted)
1. Gave your character a more dynamic pose, switched colors.
2. Original color scheme version.
3. Tossed all NES restrictions out the window. Basically, my take on the character with no limits. (Okay, not without limits, but it's me thinking more freely. You get the idea.)
Hope this gives you some ideas!