Is a pilot's instinctive reaction to a stall counter-intutive?
The correct way to recover from a stall is counter intuitive, not because pilots are trying to climb, but because the nose of the airplane drops due to the loss of lift and aircraft design.  99.999% of the time (when the aircraft is not in a stall), if the nose drops, you simply pull back in order to raise it and this muscle memory is built over time.  

Unfortunately, if the aircraft has stalled, pulling back will only worsen the situation and you need to push forward in order to gain sufficient airspeed for a recovery.

Yes, stall recovery is taught in both primary training, and during simulator training for pilots, although not typically to a full stall in the simulator.  Instead, the aircraft is slowed to the first indication of a stall which may be a stall warning system instead.  At this point they are expected to apply the correct stall recovery techniques recommended by the manufacturer / their SOP's.

There is a fairly large difference between recovering from a stall in a training environment because you know that it is coming and already know what you are going to do when it happens.  A large part of stall training is for stall recognition so that hopefully if it were to happen outside the training environment, the pilot will recognize the warning signs before it happens and can apply the proper stall recover technique before the aircraft enters a full stall.  

Unfortunately, out "in the real world" most unplanned stalls that occur happen because the pilot is distracted by something else and they aren't expecting it. That lack of anticipation sometimes causes them to fall back on muscle memory and pull up just because the nose fell without realizing what happened.  This can be more likely when the stall doesn't happen quite like it does in training.  In some situations there may be fewer warning signs, or a component of the stall warning system isn't working as expected and can delay the realization that they are in a stall.

For more information on what a stall is and why pilots practice them, see another question that was asked before here: What happens when an airplane stalls and why do pilots practice it?