Zune wasn't rejected because it was late to market.
It was rejected because Microsoft refused to give up on their lockin, and make the system open so that users could play any non-DRM'd format. Like it or not, the enforced DRM presents a serious usability issue for non-technical users. (Technical users don't care about usability problems - but they appreciate "slick" when it's there, and they appreciate ways to work around "only plays protected
Add to this; Microsoft was far-behind in terms of technical capabilities, compared to other players. (video, audio quality, etc - and later, iPod touch with apps and all that). Microsoft could have sunk enough R&D into Zune to do all that. But I think MS never really believed that they could succeed.