Like CDan, I live in the desert where there is low humidity. I never had the feed problem you speak of with this paper.
Back in the day when I worked with copy machines, any drastic change in humidity, either direction, would cause the copiers to to jam more frequently. I think it has something do to with static electricity causing the paper to cling together. Fanning the paper before putting it into the tray would help.
Try fanning the paper before loading it in the printer and see if that helps.
[B]ADDED:[/B] I just saw that you said you tried fanning the paper, oops. Be sure to fan it while holding it from different edges. A couple times from different edges should help. The humidity is definitely playing a part in your issue.