"Microsoft couldn't seem to get that right" - I think the depends on your definition of "right" is :)
The hardware and UI of the software on the Zune are (IMO) better than the iPod Touch. I enjoy the visuals of the Zune playback. I love scrolling through my artists, albums, etc. on the Zune compared to the iPod. I believe they did get that right.
I also love the Zune Marketplace. For example, I love the song "No Heaven" by Champion. Which lead me to a group called Bane. The first few listens of Bane were good. But I soon grew tired of them. They didn't have the replay value that Champion does (to me. I mean no offense to any fans). In the iTunes model, I would have to buy the music and be stuck with music I don't like. So I think that Microsoft got it right there. I know there are others that do streaming as well Last.fm, GrooveShark, etc. but I think (or least I thought) that Microsoft had the leverage and money to get a comprehensive streaming library the size of iTunes and/or Amazon MP3. And this gets into the areas where I think they failed...
Their marketing didn't exist. The only commercial I remember is some kid that traded a song with a convenience store clerk. And the only reason I remember it is because of the groan that came out of the audience that saw the commercial. I don't recall what Zune called the music sharing, but it was a stupid word. And the commercial forced its use.
And the other big fail - it feels like a hobby to Microsoft. It feels like a product that they don't care if it succeeds or not. If it does, great. If not, whatever. It's hard to get excited about a product that a company isn't even excited about.