But I'm guessing that would still take up one whole sprite palette?

Yes, it would.

No. You'd have to make use another sprite on top of it. So, if the old man was on an NES, the motion blur itself would have to be a different sprite altogether, with it's own palette.

If you really want to get technical and true to NES, all you can use is 4 sprite palettes, and each one has to have transparency as a color.
So...

Sprite palette #1 = Transparency + 3 colors
Sprite palette #2 = Transparency + 3 colors
Sprite palette #3 = Transparency + 3 colors
Sprite palette #4 = Transparency + 3 colors

So, the old man would use use Sprite palette #1, which is the skintone, red, black, and transparency. The motion blur would have to be the color, transparency, and 2 other colors. And then you only have 2 sprite palettes left for everything else. Ofcourse, you could re-use the old man palette and the motion blur palette on other things too.

It's a real pain, cause you can't just pick 16 colors and use em however you want like with old PC games.

Hm, you make a good point. The bottom 2 mock-ups seem to work much better with these sorts of palettes as opposed to the top two. I shall look for a more appropiate image test later.

Upon looking at Arne's palette and comparing it to mine, they are some similarities. Mainly, we share similar the 4 midtone red/blue/green/yellow colors. His has alot more greys and I have alot more browns in mine, though. Let's compare side-by-side.

Arne on top, mine on bottom.

Ok, I think I've got this to the point where i want it for now, at least. I'm going to upload it to the pixeljoint context. Thanks again for the help guys! It certainly helped me.