Can a normal force do work?

At the first-year physics level -- absolutely a normal force can do work.  If an object moves parallel (or antiparallel) to a normal force, then the normal force has done work.  

But how can that be?  A block slides to the left on a flat surface, say.  The normal force is upward, movement is left, so the motion is not parallel to the normal force.  No work is done by Fn.

That's correct.

Even for a block sliding up or down an incline, the normal force does no work.  The normal force by definition is perpendicular to the surface, and the block slides along the surface; no component of the normal force is parallel to the motion.

That's correct, too.

So how in the sam hill can a normal force possibly do any work?

What if the surface itself is moving?

Consider a person standing in an elevator.  The normal force is the force of the elevator floor on the person.  As the elevator moves upward, so does the person... so the normal force is parallel to the person's motion, doing work.  If the elevator moves downward, the normal force is antiparallel to the motion, and so does negative work.

Now I leave you with this... what if the elevator is slowing down as it moves upward, such that the normal force is less than the man's weight.  Does the normal force do positive work, negative work, or zero work?  I'll answer in a few days in the comment section.