The issue you are describing was actually intentionally implemented into the code. There is a fraction of a second that Mario is not able to jump again, after hitting the ground from a prior jump. You can see an animation for a few frames, of some lines back by Mario's rear/feet area, after he jumps. As long as you can see these lines, you cannot jump again. It's a very short time, but it is just enough to mess you up sometimes.
I tried playing a few games tonight and this was exactly the right advice. After he jumps, there are little sparks at the back of his feet and you cannot jump again until they go away. You have to time your jumps a little opposite of what your natural instincts are and jump a few milliseconds later rather than sooner. It almost looks like the barrel is going to run you over, but he clears it!
Thanks again mikegmi2!