OK... I have the 30gb Zune with the 3.1 firmware. I've had it a little over a year. I have just started having this restarting issue. I have totally reformatted the device and reloaded the firmware and media. I have done hareware reboots and tried the battery recondition. Still having shutdowns about 2-3 minutes after starting to listen to music UNTIL.....
I tried to do the battery reset a second time. If you follow the procedure listed in the help section, they tell you to turn the background to always on (to help drain the battery faster.) Guess what.... when I do this I don't get any shutdowns. None. So... give this a try. You'll have a lot less listening time, but should be able to go without shutdowns.
Disclaimer: This works on my 30gb.. I don't know if it will on any other model...
Jack
Fairbanks, Alaska