What bitrate and sample rate are your MP3's encoded at? Maybe you've accidentally encoded them at some nonstandard bitrate or sample rate.
I tried a few, it seems that stereo has something to do w/ it:
256kbps, stereo, 44Khz -> BAD
128kbps, stereo, 44Khz -> BAD
128kbps, mono, 44Khz -> GOOD (except for the no stereo part).
Maybe Zune just can't do stereo.