In this case, the plaid on his shirt had to go for sure. Colors that were barely used like the buckles on his overalls had to be combined with the flesh tone since you certainly couldn't lose that one! Certain shapes like his fists were changed to make them easily readable at a smaller size.
The hardest part had to have been the face, of course--there just isn't enough room to put the same shape of eyes and eyebrows, so everything came out a bit abstracted. It reads well enough as angry eyebrows and eyes, I think. The dimensions of the NES sprite are 32x40 pixels (a couple blank pixels above his head that could have probably been filled though), the same size as Donkey Kong.