But you have, in my opinion, too few colors. For a polished look, at my skill level, I needed a few more.
I hate to disagree, but this is absolutely not true. If you can't polish something with four colors, you're not going to be able to polish it with ten. It might look harsh with just four, but that's not the main point of polish. The way I see it, when you polish something, you just go through your piece and remove any unneeded details or stray pixels to keep the piece clean and readable. Color control is an invaluable skill to learn as a pixel artist (or at least, so I've read), and I think that wouldn't be such a good idea to add extra colors to his piece.
Big, important thing I forgot. drop the outlines. IMHO, it's cluttering it up and hindering your drawing space and drawing the eye too much. So yeah, that's my opinion.
I can't help but notice how ironic this statement is; you say the outlines clutter up his piece, but you fail to mention that the stripes you added, while they do add a nice touch, end up cluttering the sprite much more than an outline does, and IMHO push the sprite towards the background. It is good to break away from outlines to improve your ability to make priorities stand out, but when you're making the main character for a game, an outline might be the only thing that can stop your character from blending into the background; there are many ways to get something to stand out, like contrasting hues, simplicity against detail, and stuff like that, but when you've got a lot of things and colors going on in the background, even these can't keep your sprite away from the background.
As for your update, it's looking a million times better. There are still a few anatomical parts that are off, but shrike caught most of them. One thing nobody has mentioned yet, though, is that your cat's ears don't look connected to its head; one way to fix this would to just get rid of the outline separating the bottoms of its ears and head. The lightest shade needs to be even lighter than it is right now to really make a difference on your sprite, and I don't think that the shading on its head works; a cat's head is a little bit like a ball, and the only time the highlight should hug the edge of a surface is when the light source is behind the object, and, as the rest of your piece suggests, this isn't the case. Pretend the ears cast a little bit if a shadow onto the head, and try to shade the top of its head so that it looks more like a ball.
Another thing I notice with the shading right now is that it's too uniform for something as complex as a cat. Your highlight seems to hug the entire edge of your cat which is not good. Let's take Laser Kitty's back leg for instance; it sticks out past Laser's body, and so the highlight would extend down his leg a little bit. Since Laser's body would be slightly obscured by his(?) leg, the part right by the highlight on his leg would be darker than the surrounding area. This is only one place where the light gets jumbled up, and I'll let you figure out how to do the rest of the shading on him.
If you need more guidance, check these out;
http://www.itchy-animation.co.uk/light.htmhttp://www.itchstudios.com/psg/art_tut.htm