That happened to my first-gen Premium headphones - apparently it was a pretty common problem. The left bud died after a while and I pretty much gave up. From the sounds of it, your problem is probably with the headphones; probably either a soldering point failed or there's some sort of wire breakage inside. I'm not sure what you can do about it, but calling Zune support definitely sounds like a good idea.
__________________
|